În Evul Mediu, terenurile aflate la sud de Curtea Domnească din Iași erau acoperite de mlaștini, prin apropiere curgând râul Bahlui. După cum susține istoricul Ioan Caproșu, zona cuprinsă astăzi între strada Palat și strada Sf. Lazăr a început să se populeze mai ales în secolul al XVIII-lea, aici formându-se pe la mijlocul acelui secol un mic cartier denumit Broșteni, cu două ulițe podite - Podul Lung (Ulița Carvasaralei) și Podul Spânzurătorilor și o stradă comercială, numită Ulița Sf. Constantin, cu prăvălii cu un singur nivel.
În a doua jumătate a secolului al XVIII-lea, preotul grec Poliz din Tesalonic (Grecia) a construit cu banii săi o biserică de lemn cu hramul "Sf. Constantin" pe un loc domnesc din mahalaua Broștenilor (aflată în spatele Curții domnești din Iași), care-i fusese dăruit de domnitorul Matei Ghica (1753-1756) și apoi întărit de Scarlat Ghica (1757-1758). Tot el a împodobit biserica cu obiectele de cult necesare.
Aceste informații provin dintr-un hrisov din 1 aprilie 1766 al domnitorului Grigore al III-lea Ghica (1764-1767, 1774-1777), publicat de Nicolae Iorga. Acel document fusese emis ca urmare a plângerii făcute de preotul Poliz de la Biserica "Sf. Constantin" din mahalaua Broștenilor, în care se spunea că "fiind el preut străin, grec, de la Thesalonic, care a venit în Iași și prin silința și osteneala sa s'a apucat și cu drepți banii sei au zidit din temelie și au făcut acea sfântă biserică, împodobind-o cu toate cele trebuincioase, pe locul domnesc, pe care i l'a dat Matei-Vodă (1753-56), cu întăritură de la Scarlat-Vodă (1757-58)". Preotul sus-menționat se plângea că respectivul loc i se contesta de către mai mulți locuitori din mahalaua Broștenilor pe motiv că s-ar fi întins pe proprietățile lor. Domnitorul Grigore al III-lea Ghica a dispus ca o comisie boierească să verifice întinderea terenului dăruit de Matei Ghica.
În cartea “Pe ulițele Iașului”, Vasile Panopol relatează că bătrânul magistrat Gheorghe Dimachi își amintea că la începutul secolului al XIX-lea pe strada Palatului, până la Biserica “Sf. Constantin”, se aflau “boingii” și câteva crâșme, iar mai departe până peste podul de pe râul Bahlui erau case de toleranță, cu perdele roșii la ferestre, de la care s-ar fi tras denumirea de Podul Roșu dată acelei zone.
Biserica a fost refăcută din cărămidă și piatră în anul 1814 de către Gheorghe Catargiu, după cum atestă unele documente citate de Gheorghe Ghibănescu. Ușa de intrare în pronaos a fost confecționată de către Vanghelie Buingiul la 1 aprilie 1814, după cum atestă o placă metalică, bătută în nituri, cu următoarea inscripție în limba română cu caractere chirilice: "Această uși cu agiutoriu[l] lui D[u]mnezeu am făcuto eu Va[n]gheli[e] Buingiul 1814 april[ie] 1."
În decursul timpului, acest lăcaș de cult a cunoscut numeroase consolidări și reparații. Biserica a fost reparată radical în 1866.
Acest lăcaș de cult a funcționat ca filială a Bisericii "Sf. Nicolae Domnesc" până în 1936. După cum relatează N.A. Bogdan, după restaurarea Bisericii "Sf. Nicolae Domnesc", icoana Sf. Mina (considerată a fi făcătoare de minuni și vindecătoare de boli) a fost mutată la biserica filială cu hramul "Sf. Constantin și Elena" și apoi la Biserica "Sf. Andrei".
La începutul secolului al XX-lea, biserica era subvenționată de Primărie, ea neavând niciun venit propriu. În anul 1936, Biserica "Sf. Constantin și Elena" a devenit biserică parohială. Lăcașul de cult a fost pictat în interior, în tehnica frescă, între anii 1969-1974.
Începând din 1999 s-au efectuat o serie de lucrări de reparații, renovare și extindere ale edificiului bisericii, sub supravegherea preotului paroh Ștefan Ropotă. În 1999 s-a înlocuit catapeteasma veche cu una nouă, din lemn de stejar și de trandafir. Biserica a fost extinsă prin adăugarea unui nou pridvor de aproape 150 metri pătrați. Pereții exteriori ai bisericii au fost reparați și zugrăviți, s-a înlocuit în întregime acoperișul, atât tâmplăria din lemn, cât și învelitoarea de tablă și s-a montat o ușă monumentală din fier, cu elemente de bronz turnate. În interior, s-a renovat pictura interioară a bisericii și s-a reparat Sfânta Masă.
După finalizarea acestor lucrări, lăcașul de cult a fost resfințit la 18 mai 2003 de către un sobor de preoți și diaconi în frunte cu mitropolitul Daniel Ciobotea al Moldovei și Bucovinei, care au oficiat slujba pe o scenă amenajată în afara bisericii. Cu această ocazie s-a resfințit și altarul, ca urmare a faptului că fusese reparată și Sfânta Masă. La acesta ceremonie au participat peste 1.000 ieșeni.
La 21 mai 2009, de sărbătoarea hramului, Sfânta Liturghie a fost celebrată de mitropolitul Teofan Savu al Moldovei și Bucovinei, înconjurat de un sobor de 12 preoți și diaconi. La acestă slujbă religioasă au participat peste 300 de credincioși, răspunsurile la strană fiind date de membrii Corului „Basileus“ al Seminarului Teologic Liceal Ortodox „Sf. Vasile cel Mare“, dirijat de prof. Mihai Ursachi. Tot cu acest prilej, mitropolitul Teofan a săvârșit și o hirotonie a unui diacon.
Arhitectura bisericii
Biserica are ziduri groase. Intrarea în biserică se face prin două uși, una situată în peretele vestic al pridvorului și a doua în peretele sudic al altarului.
Interiorul bisericii este compartimentat în pridvor (adăugat recent), pronaos, naos și altar. În pridvor se intră printr-o ușă masiv de fier. Deasupra intrării se află o icoană în mozaic a Sfinților Împărați Constantin și Elena. Din pridvor se intră în pronaos printr-o ușă de fier pe care se află o inscripție cu caractere chirilice. Pronaosul este separat de naos prin două coloane circulare ce sprijină trei arcade. La etajul superior al pronaosului se află cafasul, unde se accede printr-o ușă aflată în peretele nordic al pronaosului care duce la o scară. Deasupra pronaosului se înalță un turn-clopotniță de secțiune pătrată. În peretele nordic al naosului se află o altă ușă.
