Pierwsza wzmianka o Kościele Świętego Mikołaja w Skwierzynie (wówczas była to osada o nazwie Skwirzyna) pochodzi z 1226 roku. Mniej więcej z tego okresu pochodzi część murów w prezbiterium, które w szczątkowej postaci zachowały się do dziś. Domniema się, że pierwotnie świątynia zbudowana była w znacznym stopniu z drewna. Jednak w XV wieku wybudowano nowy budynek na miejscu starego kościoła, tym razem w całości z cegły. Plan ówczesnego budynku pokrywa się niemal w całości z dzisiejszym kształtem świątyni. W 1507 patronem kościoła został św. Mikołaj Biskup. 33 lata później, w 1540 Kościół Świętego Mikołaja stał się świątynią protestancką. W tym czasie większość mieszkańców Skwierzyny była właśnie tego wyznania. W związku z tym starosta międzyrzecki Stanisław Myszkowski przekazał w ich ręce kościół. Stan taki utrzymywał się do 1605, kiedy to biskup poznański Wawrzyniec Goślicki interweniował u starosty międzyrzeckiego Jan Zamojski w sprawie kościoła. Dostojnik kościelny zażądał, aby świątynia powróciła ponownie w posiadanie katolików. Świątynia wielokrotnie cierpiała z powodu pożarów, które nawiedzały całe miasto (m.in. w 1624 i 1712). Gruntowna przebudowa budynku nastąpiła w latach 1861-1863. Uzyskał on dzisiejszy kształt. Nowa budowla została konsekrowana 17 maja 1863 przez biskupa pomocniczego poznańskiego Franciszka Stefanowicza. Kościół uniknął spalenia po wkroczeniu do miasta Sowietów w 1945 roku, ponieważ urządzili oni wewnątrz świątyni magazyn rekwirowanego mieszkańcom różnorakiego sprzętu. Po II wojnie światowej Skwierzyna znalazła się w granicach Polski. Pierwszym polskim proboszczem po 1945 został ojciec Felicjan Gomółczak (Bernardyn). Jednak już w listopadzie tego samego roku kościół i całą parafię przejęło Zgromadzenie Księży Misjonarzy (administrują oni Kościołem Świętego Mikołaja do dnia dzisiejszego). Zaraz po wojnie w kościele znalazł się Obraz Matki Boskiej Klewańskiej, przywieziony potajemnie przez polskich repatriantów z Klewania na Wołyniu. W obawie przed komunistami był on ukrywany przez szereg lat, a jego oficjalne umieszczenie w ołtarzu głównym kościoła miało miejsce w 1968.