Najstarsze dostępne źródła podają, że Paruszka założona została na początku XVII wieku. W 1652 roku mieszkało tutaj 26 rodzin chłopskich, a wszyscy byli kolonistami niemieckimi i protestantami. Kilkadziesiąt lat później dżuma zdziesiątkowała mieszkańców wsi, a na ich miejsce sprowadzono kolonistów holenderskich, w większości również protestantów. Na początku XVII wieku miejscowi protestanci wybudowali sobie małą kapliczkę z drewna, którą kilkadziesiąt lat później utracili na rzecz parafii katolickiej w Głubczynie. Filia głubczyńskiego kościoła czciła św. Filipa, przeznaczona była dla katolików, ale protestanci nadal z niej korzystali. W każdą niedzielę szli na swoją mszę odprawianą w języku niemieckim przez nauczyciela tutejszej szkoły protestanckiej. Wspólna świątynia nie podzieliła jednak protestantów i katolików, wręcz przeciwnie: nauczyła ich tolerancji i współpracy. Drewnianą kaplicę w końcu XIX stulecia zastąpił murowany kościół w stylu neogotyckim, który przetrwał do dziś i powierza wiernych opiece św. Serca Jezusowego.
W starych księgach chrztów od 1693 roku wpisywano chrzty, śluby i pogrzeby z wioski Paruszka. Paruszka należała do parafii św. Trójcy w Głubczynie. Pierwsza wiadomość dotycząca owej parafii sięga roku 1588, w którym opat pleszniewski Andrzej Kościelec Kościelecki, wlaściciel dóbr głubczyńskich, zakłada parafię głubczyńską, fundując kościół i probostwo. Tę parafię zatwierdził arcybiskup gnieźnieński Stanisław Karukowski 02.04.1588 roku. Do niej należały kaplice w Starem, Paruszce i Sokolnie.
Duszpasterską posługę w parafii w latach 1908- 1930, piastował ks. proboszcz Maksymilian Grochowski. Odegrał on ogromną rolę w utrzymaniu polskości w okresie międzywojennym.
Po ks. Janie Lisie proboszczem parafii Głubczyn został ks. Józef Pałka, który objął pieczę nad kościołem filialnym w Paruszce. Sumiennie spełniał obowiązki duszpasterskie. Dbał o katechizację dzieci. Wybudował na chórze w kościele specjalną salkę do nauki religii.
Ksiądz Józef Pałka odszedł z parafii Głubczyn w 1967 roku.
Jego następcą został ks. Jan Meger, który był proboszczem parafii do 1980 roku. Dojeżdżał do Paruszki własnym samochodem odprawiać msze św. w niedziele i święta. Ks. Jan Meger odszedł na emeryturę i zamieszkał w kupionym przez siebie domku w Skórce. Zmarł jako emeryt 17.04.1991 roku w szpitalu w Złotowie. Spoczywa na cmentarzu przykościelnym w Głubczynie.
Kolejnym proboszczem był ks. Jerzy Domin, który pełnił funkcję od 1980 roku. do 30.06.1987. W czasie duszpasterzowania ks. J. Domina, w 1981 roku została przeprowadzona wizytacja biskupia przez ks. biskupa Tadeusza Werno. Wizytacja połączona była z udzieleniem sakramentu bierzmowania. Ks. Domin przeprowadził remont kościoła w Paruszce, a jego okna przyozdobił witrażami.
Następnym duszpasterzem parafii Głubczyn został ks. Eugeniusz Mackowicz, który funkcję proboszcza pełnił od 01. 07.1987 roku do 01.07.1997 roku, czyli równe 10 lat. W tym czasie parafia Głubczyn, a więc i Paruszka jako jej filia, przeżyła dwie wizytacje biskupie. Pierwszej w 1988 roku dokonywał ks. biskup Piotr Krupa, a drugiej w 1995, ks. biskup Paweł Cieślik.
25 kwietnia 1990 roku Paruszka przeżyła peregrynację (wędrówkę) Obrazu Matki Boskiej Częstochowskiej, której przewodniczył ks. biskup Ignacy Jeż, ówczesny ordynariusz diecezji.
W czasie dziesięciolecia ks. Mackowicza, kościół w Paruszce wzbogacił się o nowe lichtarze ołtarzowe, organy i nagłośnienie, nowe ornaty, alby i bieliznę ołtarzową, lichtarz pod paschał, wykładzinę w prezbiterium. Odnowiono również kielich i puszkę. W tym czasie dokonano też remontu kościoła. (c.d.n.)