Potrivit pisaniei pictate la intrarea în Biserica „Sfântul Vasile cel Mare“ din cartierul Nicolina, sfântul lăcaş s-a zidit „cu vrerea Tatălui ceresc, Celui în Treime slăvit“, între anii 1795-1829, de către ieromonahul Vartolomeu.
În decursul timpului, biserica a necesitat succesive reparaţii, fiind complet reînoită între anii 1984-2005. Pictura a fost executată de către Costin şi Zenaida Răcheriu, în anul 2005. Lucrările de reparaţii la Biserica „Sfântul Vasile cel Mare“ au fost începute pe 7 februarie 2003, cu binecuvântarea Preafericitului Părinte Patriarh Daniel, pe atunci Mitropolit al Moldovei şi Bucovinei şi au continuat până la sfârşitul anului 2007, când părintele Vasile Ungureanu a ieşit la pensie.
În timpul păstoririi părintelui Vasile Ungureanu, biserica a suferit reparaţii şi îmbunătăţiri. În sensul acesta, s-a sfinţit o capelă care s-a construit lipită de trunchiul dinspre nord al bisericii, care a servit ca praznicar, iar ulterior a fost transformată în capelă pentru depunerea celor răposaţi. Donatorul principal al acestei capele a fost familia domnului Lazăr Costică. În anii din urmă, s-a construit o capelă adiacentă, simetrică cu cea de la nord, pe peretele de sud al bisericii, care serveşte acum ca praznicar. Tot aici, părintele paroh desfăşoară activităţi cu diferite grupuri sociale din parohie. Această capelă a fost ridicată prin bunăvoiţa familiei domnului Ianul Vasile. Acoperişul vechi al bisericii a fost schimbat în anul 2003 cu unul de tablă zincată, actualmente forma acestuia este cea specifică bisericilor ştefaniene.
Cimitirul parohial al Bisericii „Sfântul Vasile cel Mare“ - Nicolina a fost reînfiinţat în anul 2005 cu binecuvântarea PF Patriarh Daniel, pe atunci Mitropolit la Iaşi.
Printre obiectele de cult care au fost restaurate se numără icoana Maicii Domnului, a sfinţilor Mitrofan, patriarhul Constantinopolului, Teodosie cel Mare, începătorul vieţii de obşte. Curtea Bisericii „Sfântul Vasile cel Mare“ a fost pregătită pentru a-i primi pe credincioşii care vor asista la sjluba de resfinţire şi, mai apoi, la Sfânta Liturghie arhierească. Au fost vopsite toate gardurile bisericii, atât cele care delimitează la exterior curtea bisericii, cât şi cele care delimitează curtea bisericii de curtea casei parohiale, iar monumentul eroilor din cimitirul aflat lângă biserică a fost curăţat.
