Kościół znajduje się w centrum miasta, przy dawnym rynku głównym, obecnie pl. Wolności, w pobliżu ratusza.

W 1303 roku, 23 kwietnia, został podpisany przywilej lokacyjny miasta Wałcza. W dokumencie tym jest również mowa o kościele parafialnym, który ma być obdarzony licznymi dobrami, m.in. 4 łanami roli.

Ten pierwszy wałecki kościół został zbudowany w miejscu, gdzie obecnie stoi kościół pw. św. Mikołaja. Był to zapewne niewielki budynek wzniesiony z drewna, który spłonął w 1378 roku. Kolejny budynek mógł być już częściowo z drewna a częściowo z kamienia ciosanego. W 1863 roku rozpoczęto budowę obecnego kościoła w stylu neogotyckim, orientowanego z przesunięciem osi wschód – zachód w kierunku południowym. Ze starego kościoła przeniesiono cztery dzwony, najstarszy z nich pochodził z roku 1659. Budowa kościoła została zakończona w 1865 lub 1866 r.  Za każdym razem kościół budowano w obrębie starego miasta, na placu kościelnym przy rynku miejskim. Budynek wzniesiono na fundamencie z naturalnego kamienia, obrobionego w prostopadłościenne bloki, które były łączone zaprawą wapienną. Ściany murowano z cegły ceramicznej pełnej na zaprawie wapiennej, przy zachowaniu wątku krzyżowego. Jest to dobrze zachowane do obecnych czasów, kościół nigdy nie był tynkowany z zewnątrz. Ściany wewnętrzne są obecnie w całości otynkowane w dobrze dobranych kolorach: jasnym ugrem, jasnym brązem i ciemniejszym brązem, ciemniejszymi kolorem wyróżnione zostały wnęki i filary. Początkowo ściany pokryte były freskami, prawdopodobnie w wykonaniu znanego malarza Paula Stankiewicza.

Kościół zbudowany jest na planie krzyża łacińskiego, z prostokątną nawą główną 4-przęsłową, przeciętą nawą poprzeczną, czyli transeptem. Po stronie południowo-wschodniej znajduje się pięciobocznie zamknięte prezbiterium. Posiada ono symetrycznie umieszczone po dwóch bokach aneksy, przeznaczone na zakrystie. W nawie, transepcie i w prezbiterium widoczne są piękne sklepienia krzyżowo–żebrowe, zaś w kruchcie zastosowano sklepienia krzyżowe. Prezbiterium oddzielone jest od nawy i transeptu szerokim, ostrołukowym, ciekawie wyprofilowanym łukiem tęczowym.

Okna nawy i transeptu wypełnione współcześnie wykonanymi witrażami figuralnymi.
W transepcie od strony południowej przedstawiono postacie świętych: św. Józefa Cieślę, św. Brata Alberta, św. Dominika Savio. W nawie pod emporą organową widnieje „Powrót syna marnotrawnego”, a po stronie przeciwnej św. Maria Magdalena. W transepcie po stronie północnej witraże obrazują Matkę Boską Fatimską, NMP z Lourdes oraz MB Ostrobramską. W prezbiterium witraże prezentują Sakramenty Kościoła: Eucharystii, Pokuty i Pojednania, Namaszczenia Chorych, Chrztu oraz Bierzmowania. W oknach nawy, w ścianie południowej znajdują się postacie: św. Wojciecha i św. Maksymiliana Marii Kolbego, św. Ignacego Loyoli i św. Stanisława Kostki. W witrażach na emporze organowej umieszczono św. Grzegorza i św. Cecylię. Po stronie północnej witraże przedstawiają postacie bł. Teresy Ledóchowskiej i św. Teresy od Dzieciątka Jezus, św. Teresę i św. Jadwigę Śląską. W transepcie północnym Matka Boska Skrzatuska, Matka Boska jako Gwiazda Morza i Ucieczka Grzeszników. W transepcie południowym: postacie św. Mikołaja i św. Stanisława, Matka Boska Królowa Polski, Jasna Góra, przeor Kordecki, król Jan Kazimierz, śluby Jasnogórskie, Matka Boska Matka Kościoła, widok Bazyliki św. Piotra, papież Jan Paweł II, widoki katedry koszalińskiej i konkatedry kołobrzeskiej.

We wnętrzu kościoła zachowały się z czasów powstania świątyni: neogotyckie ławy kościelne, organy o neogotyckim prospekcie II-kondygnacyjnym, 5-osiowym, wykonanym przez P.B. Voelknera, neogotycka chrzcielnica, mosiężny 21 ramienny świecznik typu korona oraz dwa obrazy autorstwa Paula Stankiewicza z lat 60-tych XIX w.: św. Cecylia i św. Antoni. Reszta wyposażenia jest współczesna: ołtarz główny z piaskowca z elementami metaloplastyki pochodzi z 1974 r., ołtarze boczne - ołtarz MB Nieustającej Pomocy i ołtarz św. Mikołaja z 1975 r.

Kościół został konsekrowany w 1866 r.