Wieś Koczała była starą słowiańską osadą. Początkowo była wsią szlachecką, a później gromadzką. Pierwsza wzmianka historyczna o niej pochodzi z 30 listopada 1356 roku, z aktu donacji dokonanej przez rycerza Aleksandra Stanko ze Strzeczony, którego ród wywodził się z najbliższego otoczenia księcia gdańskiego Mściwoja (Mestwina) II. Drugi dokument dotyczący Koczały pochodzi z roku 1378 i wydany został przez Piotra Stanko, syna Aleksandra, jego matkę i braci.

Parafia katolicka w Koczale powstała prawdopodobnie w roku 1356 roku, kiedy to wspomniany rycerz Aleksander Stanko ofiarował jej proboszczowi cztery włóki ziemi. Parafia była zawsze w posiadaniu katolików. W XVI wieku kościół w Koczale, jako parafialny dla bardzo rozległej okolicy, aż po Miastko i Biały Bór, pełnił rolę głównego ośrodka duszpasterskiego dla katolików. W okresie rządów kanclerza Bismarcka wysiedlono do Nadrenii mieszkających tu Polaków, a na ich miejsce sprowadzono Niemców - protestantów, dla których wybudowano w miejscu rezydencji dworskiej zbór, który po wojnie został rozebrany.

Parafia rzymskokatolicka pw. Narodzenia Najświętszej Maryi Panny w Koczale znajduje się na terenie dekanatu Miastko, w diecezji koszalińsko-kołobrzeskiej. Do parafii należą miejscowości: Bielsko, Bryle, Dymin, Działek, Dźwierzno, Kałka, Koczała, Lipczynek, Łękinia, Niedźwiady, Niesiłowo, Ostrówek, Płocicz, Podlesie, Potoki, Starzno, Szyszka, Świerkówko, Załęże, Żołna, Żukowo. Wspólnota parafialna liczy około 3100 wiernych. Oprócz kościoła parafialnego pw. Narodzenia Najświętszej Maryi Panny w Koczale, do parafii należą także kościoły filialne pw. św. Mikołaja w Starznie i pw. św. Floriana w Bielsku.

Poprzedni proboszczowie: ks. Rocliński (1720), ks. Pothun (1737), ks. Linke (1765), ks. Warecki (1785), ks. Koenig (1804), ks. Pick (1814), ks. Hoppe (1829), ks. Otto Gronau (1862-1911), ks. Franciszek Spors (1911-1936), ks. Maksymilian Münchbera (1937-1947), ks. Jan Dec (1947), ks. Władysław Holak (1947-1974), ks. Jan Szmelter (1974-1991), ks. Lech Bończa-Bystrzycki (1991-administrator), ks. Kazimierz Gierszewski (1991-1998), ks. Józef Oleski (1998-2016).

Poprzedni wikariusze: ks. Dariusz Kasiński (2004-2006), ks. Jacek Dziadosz (2006-2007), ks. Marcin Gajowniczek (2007-2011), ks. Sebastian Maciuszko (2011-2016), ks. Andrzej Szewczyk (2016-2018).

Kapłani pochowani na miejscowych cmentarzach: ks. Otto Gronau, ks. Franciszek Spors, ks. Władysław Holak.

Powołania kapłańskie i zakonne z parafii: ks. Rafał Zabłoński, ks. Daniel Hinc (zmartwychwstaniec- aktualnie misjonarz w Tanzanii), śp. ks. Arkadiusz Stępień (zmartwychwstaniec), br. Zbigniew Minko (brat szkolny), śp. s. Radosława Niezdropa (klaryska), śp. s. Kazimiera Ważna (karmelitanka bosa).