Biserica parohială cu hramul „Sf. Nicolae” din Truşeşti a fost zidită în anul 1839 de către Preacuviosul Iero-arhimandrit Nicodim Asfaketalonitul, egumenul Mănăstirii „Sfinţii Trei Ierarhi” din Iaşi, prin stăruiala boierilor Vasile şi Safta Lepădatul şi osteneala locuitorilor din Truşeşti, după cum găsim scris în pisania inscripţionată deasupra uşii de intrare în Sfântul locaş.
Din mărturiile culese de la bătrânii satului aflăm că la început Biserica a fost zidită din cărămidă şi acoperită cu şindrilă, având numai altar, naos şi clopotniţa cu geamuri mici. Odată cu venirea ca paroh a preotului Dumitru Teodorescu, în anul 1893, după reparaţii capitale, biserica ajunge la forma de cruce în care se găseşte şi astăzi (Altar, Naos, Pronaos), zidită pe o suprafaţă de 110 m.p. În anul 1913, antreprenorul Dumitru Gheorghiu doreşte să renoveze Biserica, dar, din cauza primului război mondial, amână aceste lucrări până în anul 1920, când, în timpul primarului Petrache Grigoraş, Biserica este renovată capital atât la interior, cât şi la exterior. Interiorul este zugrăvit în ulei, cu chenare decorative şi diferite picturi murale executate de pictorul Victor Galin. Se confecţionează o nouă Catapeteasmă, Strana Arhierească şi Strana Maicii Domnului. Se înlocuiesc geamurile existente cu geamuri mai mari şi se înalţă Biserica cu un metru. Tot atunci se construieşte Cafasul, se adaugă Pridvorul şi se acoperă Biserica cu tablă, Catapeteasma şi icoanele vechi fiind donate Bisericii din Strahotin.
Între anii 1928-1950, în timpul păstoririi preotului Vasile Rugescu, maistrul lemnar Jan Ailenei confecţionează stranele pentru credincioşi, în număr de 35.
În anul 1950 se înfiinţează Raionul Truşeşti şi Protopopiatul Truşeşti, paroh şi protopop fiind numit preotul Gheorghe Vasiliu care face şi el mici reparaţii la biserica parohială. În anul 1965, preotul Gheorghe Vieru face reparaţii interioare şi exterioare, lucrări continuate, mai apoi, de către preotul Constantin Bunduc.
În perioada 1982-2003, parohia a fost păstorită de preotul Emil Stroişteanu care a desfăşurat ample lucrări de reparaţii interioare şi exterioare. Cu binecuvântarea P.F. Daniel, pe atunci mitropolit al Moldovei şi Bucovinei, Biserica nou pictată este resfinţită în ziua de 15 noiembrie 1992 de către P.S. Calinic Botoşăneanul.
În anul 1991 se reînfiinţează Protopopiatul Truşeşti care funcţionează până în luna septembrie a anului 1999.
Din anul 2004, paroh este numit preotul Florin Hălăucă. Acesta renovează vechea casă şi curte parohială în proporţie de 60% şi dotează locaşul de cult cu cele trebuincioase în vederea desfăşurării în bune condiţii a actului liturgic (veşminte preoţeşti, Sfânta Evanghelie, Sfinte Vase, Sfântul Chivot, Sfinte Cruci, sfeşnice, candele, cărţi de cult, covoare, etc). Este reamenajat interiorul Bisericii, este schimbată vechea tâmplărie cu tâmplărie tip termopan, este achiziţionată o staţie de amplificare şi este confecţionat un lumânărar. În curtea Bisericii se construieşte în această perioadă o casă socială (formată din sală de prăznuire, cameră mortuară, bucătărie, grupuri sanitare, bibliotecă, birou parohial, cameră pentru activităţi cu tinerii şi copiii) la care se lucrează încă.
În ordine cronologică, preoţii care au călăuzit credincioşii şi au slujit în această Biserică au fost Pr. Gheorghe Bordei, Pr. Constantin Ciacâru, Pr. Enache Perdevară, Pr. Dumitru Teodorescu, Pr. Vasile Rugescu, Pr. Gheorghe Vasiliu, Pr. Gheorghe Vieru, Pr. Constantin Bunduc, Pr. Emil Stroişteanu şi , în prezent, Pr. Florin Hălăucă.
