Potrivit tradiției, prima biserică în Târgu Neamț a fost înălțată în vremea domniei lui Ștefan cel Mare, poate chiar de el. Din cauza vitregiilor vremii (războaie, incendii) biserica a avut mult de suferit, fiind necesare dese reparații, în cele din urmă dispărând definitiv. Prima mențiune documentară despre biserica Adormirii datează din timpul domnitorului Gheorghe Ștefan (1653-1658). Este vorba de un zapis din 7 februarie 1677, referitor la vânzarea unei moșii, zapis în care apare și numele preotului de la biserică, Toader. De la biserica atribuită domnitorului Gheorghe Ștefan a fost furată de tătari în 1717 o Evanghelie tipărită de Șerban Cantacuzino în anul 1682. Evanghelia a fost răscumpărată de preotul Vasile și soția sa, Maria.
Biserica lui Gheorghe Ștefan, care a fost construită din lemn pe temelie de piatră, nu a rezistat decât până în prima jumătate a secolului XVIII-lea, fiind deteriorată, fie din cauza conflictelor armate care s-au desfășurat în această perioadă, fie din cauza incendiilor care se produceau destul de des, fiind nevoie de a fi refăcută.
Potrivit Sinodicului (scurt istoric) bisericii, aceasta a fost rectitorită de domnitorul Moldovei Grigore II Ghica, în timpul celei de a IV-a domnii (1747-1748), fiind sfințită în 1747 de mitropolitul Nichifor al Moldovei. Biserica refăcută de Grigore II Ghica nu a rezistat nici ea decât 62 de ani, fiind „prefăcută din nou” în anul 1809 de ctitorul Ștefan Velea din Târgu Neamț, la refacerea ei contribuind și credincioșii din târg, fiind sfințită de Mitropolitul Veniamin Costachi în același an (1809). Această biserică a fost ultima ridicată din lemn pe temelie de piatră, fiind distrusă complet de incendiul ce a izbucnit în 14 aprilie 1864, orele 3 dimineața (noaptea Învierii Domnului).
După dispariția bisericii, preoții și credincioșii s-au organizat în vederea ridicării unui nou sfânt locaș. Construirea actualei biserici a început în anul 1867, prin contribuțiile bănești ale credincioșilor din oraș, și au continuat până în anul 1872 când, din cauza lipsei de bani, lucrările au încetat. Acestea au putut fi reluate datorită ajutorului dat de un bun creștin din Piatra Neamț, boierul Nicolae Albu, fost prefect al județului, și soția sa Calipso care, „văzând lucrarea și credința poporului, dar și supărarea lor că nu pot continua ridicarea monumentalei biserici au dăruit un ajutor de 500 de galbeni, și așa biserica s-a apropiat de sfârșit”. Lucrările au fost finalizate în anul 1875, biserica fiind sfințită în ziua de 10 august a anului respectiv de către Mitropolitul Iosif Naniescu, fiind prima biserică de parohie sfințită de el după întronizarea sa ca mitropolit al Moldovei (6 iulie 1875).
Biserica este construită din piatră și cărămidă după planurile arhitectului Johan Brandel de Daggendorf, originar din Bavaria – Germania, fiind o podoabă arhitectonică a orașului.
Actuala pictură a bisericii s-a realizat între anii 1990-1998 de către pictorul Ion Preutu, împreună cu colaboratorii Doina Preutu, Eugenia Popescu, Constantin Ignat, și Ciprian Istrate. Pictura a început sub preoții Constantin Grigoriu Și Constantin Vasilescu, iar din 1995 a fost continuată de preotul Vasile Ignătescu.
După terminarea picturii biserica a fost sfințită în data de 18 octombrie 1998 de către Preafericitul Părinte Daniel, Patriarhul României, pe atunci Mitropolitul Moldovei și a Bucovinei, împreună cu Înaltpreasfințitul Petru al Basarabiei.