În perioada 1839-1842 se construiește în târgul Mihăileni biserica „Sfântul Nicolae”, clădire din piatră și cărămidă, cu cheltuiala domnitorului Mihail Gr. Sturza și Smaranda doamna, sub îndrumarea banului Mihalache Mavrodin.
Această biserică a suportat reparații în 1869, când s-a reparat acoperișul și, în parte, interiorul. În noaptea de 24-25 aprilie 1872 un incendiu, care a ars mare parte din casele târgului, a ars și acoperișul bisericii cu clopotnița, topind clopotele, dar nu a afectat interiorul bisericii.
În același an biserica a fost reparată cu cheltuiala comunei și a unor binefăcători. În anul 1891, în timpul primarului Grigore Calcăntraur, biserica s-a tencuit în interior și exterior și s-au pus strane. În anul 1896 s-au făcut picturile interioare cu suma de 3.000 lei donată de familia Boureanu, s-au cumpărat obiecte de cult și veșminte.
Nu se poate preciza numele și numărul preoților slujitori de la biserica din Mihăileni pe baza documentelor decât sporadic și pentru perioade mai târzii. Dintr-o jalbă a lui Costache Țâră din satul Cândești, din 24 iulie 1855, aflăm că la Mihăileni era preotul Vasile, care îi datora reclamantului niște bani, dar la 6 noiembrie 1855 preotul iconom Cozmovici Ioan de la Mihăileni semna o învoială dintre soți.
În anul 1874 la biserica „Sfântul Nicolae” din târgul Mihăileni slujeau preotul iconom Gheorghiciu Ioan și preotul iconom Cosmovici Ioan, iar în anul 1893 aici slujeau preotul iconom Alexandrescu Neculai, de 45 ani și preotul Enescu Ioan, de 31 ani, care slujeau aici și în 1894.
În anul 1900 preotul Enescu Ioan este transferat la Biserica „Sfântul Nicolae” din Dorohoi, unde slujea în 1910 și 1930, iar la Mihăileni rămâne numai preotul Alexandrescu Neculai, care slujea și în 1910, când Parohia Mihăileni avea biserica parohială „Sfântul Nicolae” și filie capela de la cimitirul Mihăileni, cu hramul „Dumineca tuturor sfinților”, construcție de cărămidă pe temelii de piatră, realizată în 1881, cu cheltuiala comunei și a obștii din Mihăileni și înzestrată cu catapeteasma făcută și pictată cu cheltuiala defunctei Ruxanda Dohaten, născută Calmuschi.
În anul 1930 Parohia Mihăileni cu filiile Vlădeni și Pârâul-Negru avea 250 familii cu 2091 suflete și paroh pe preotul Afrăsinei Dumitru, urmat de preotul Enache Mihai, refugiat în sudul țării în perioada celui de-al doilea război mondial, de unde va reveni mai târziu, iar la Mihăileni a fost paroh preotul Anton Dumitru în perioada 1943-1974 urmat, de la 1 septembrie 1974, de preotul Tudosie Pavel până în august 1994, când acesta trece la Parohia Dersca, iar la Mihăileni vine paroh preotul Voloc Marian.
