Skwierzyna jest jednym z miast województwa lubuskiego o najstarszym rodowodzie. W pobliżu przeprawy na Warcie już kilka wieków przed narodzeniem Chrystusa istniała osada plemienna. Świadczą o tym przedmioty znalezione podczas prowadzonych wykopalisk archeologicznych. Zalążki przyszłego miasta powstały prawdopodobnie w początkach XIII wieku.
Ponieważ nie zachowały się dokumenty lokacyjne jedna z hipotez przyjmuje, że prawa miejskie Skwierzynie nadał książę wielkopolski Przemysł II przed 1296 r. Na pewno istniała już wtedy świątynia w miejscu dzisiejszego kościoła parafialnego pw. św. Mikołaja Biskupa, o której wspominają zachowane pisma z 1226 r. Dziś jest to najstarszy budynek miasta.
Istniejąca w XIII-wiecznej Skwierzynie świątynia była prawdopodobnie budowlą murowano-drewnianą. Nietrwałe materiały były powodem jej degradacji, która doprowadziła do budowy w początkach XV wieku nowego kościoła na zrębach poprzednika. Do dziś zachowały się fragmenty najstarszych murów w prezbiterium.
Nowy kościół w 1507 r. otrzymał za patrona św. Mikołaja Biskupa. W 1540 r., kiedy większość mieszkańców miasta przeszła na luteranizm świątynię odebrano katolikom. Ewangelicy pozostawali we władaniu budowli do początków XVII wieku. Interwencje katolickich władz kościelnych skutkowały zwrotem świątyni.
Kościół św. Mikołaja wielokrotnie płonął w pożarach miasta, ucierpiał zwłaszcza w 1624 – 1712 r. Ostatnia wielka przebudowa obiektu odbyła się w latach 1861-1863, w której efekcie świątynia otrzymała dzisiejsze wielkość i wygląd. Składający się z trzech naw kościół zachował jednak późnogotyckie rysy. Z tego okresu pochodzi także większość dzisiejszego wyposażenia wnętrza.