Historię parafii na bydgoskich Wyżynach B-1 i B-2 tworzy sama jej Patronka, ponieważ ważne fakty powstania i rozwoju związane są z Matką Bożą. W wigilię uroczystości Matki Bożej Częstochowskiej 25 sierpnia 1992 r. przybył na Wyżyny Ks. Józef Orchowski z zamiarem utworzenia ośrodka duszpasterskiego w tej części miasta Bydgoszczy.
Parafia powstała w czasie obchodów 75 rocznicy objawień w Cova da Iria w Fatimie. Dekret ks. abp. gnieźnieńskiego Henryka Muszyńskiego, erygujący parafię, nosił datę 8 grudnia 1992 r. – uroczystość Niepokalanego Poczęcia NMP. W następnym zaś roku, również 8 grudnia, Ks. Arcybiskup poświęcił figurę Niepokalanego Serca NMP, ufundowaną przez mieszkankę Filipin oraz trzy dzwony noszące nazwy:
- Najświętsze Serce Jezusa,
- Niepokalane Serce Maryi,
- Oblubieńcze Serce Józefa
wzywające do modlitwy i obwieszczające chwałę Boga Trójjedynego i Niepokalanej na tym skrawku ziemi bydgoskiej.
W dniu 1 stycznia 1993 r., uroczystość Macierzyństwa NMP, idąc za wezwaniem Maryi z Fatimy – „odmawiajcie codziennie różaniec”, wprowadzono codzienne odmawianie różańca o godz. 18.00, który najpierw prowadzony był kolejno przez różne grupy modlitewne. Obecnie codziennie odmawiane są cztery części różańca: w dni powszednie o godz. 6.30, 12.00, 15.00 i 18.00; a w niedziele o godz. 7.30, 9.00, 12.00 i 18.00.
W następnym roku, także w uroczystość Macierzyństwa NMP, zostały wprowadzone nabożeństwa pierwszych sobót miesiąca. Bowiem osiem lat po zakończeniu fatimskich objawień Matka Boża zezwoliła siostrze Łucji na ujawnienie treści drugiej części tajemnicy fatimskiej. Jej przedmiotem było nabożeństwo do Niepokalanego Serca NMP. 10 grudnia 1925 r. Maryja powiedziała: “Córko moja, spójrz, Serce moje otoczone cierniami, którymi niewdzięczni ludzie przez bluźnierstwa i niewdzięczność stale ranią. Przynajmniej ty staraj się nieść mi radość i oznajmij w moim imieniu, że przybędę w godzinie śmierci z łaskami potrzebnymi do zbawienia do tych wszystkich, którzy przez pięć miesięcy w pierwsze soboty odprawią spowiedź, przyjmą Komunię Świętą, odmówią jeden Różaniec i przez piętnaście minut rozmyślania nad piętnastu tajemnicami różańcowymi towarzyszyć mi będą w intencji zadośćuczynienia”. Parafia podjęła to maryjne wezwanie i jest mu wierna. W każdą I sobotę miesiąca o godz. 12.00 wynagradza Niepokalanemu Sercu Maryi, które jest obrażane przez:
- obelgi przeciw Niepokalanemu Poczęciu,
- przeciw Jej Dziewictwu,
- przeciw Jej Bożemu Macierzyństwu,
- obelgi, przez które usiłuje się wpoić w serca dzieci obojętność, wzgardę, a nawet nienawiść wobec nieskalanej Matki,
- bluźnierstwa, które znieważają Maryję w Jej świętych wizerunkach.
Natomiast 7 października tego samego roku, w dzień Matki Bożej Różańcowej podczas uroczystej Mszy św. celebrowanej przez ks. bp. Bogdana Wojtusia, został poświęcony złoty różaniec.
Matka Boża z Fatimy, wzywająca do rozkochania się w modlitwie różańcowej otaczana była wielką czcią, którą parafianie wyrazili przez piękną złotą koronę, ozdobioną koralami i turkusami, którą poświęcił ks. bp. Jan Nowak w Uroczystość Patronalną 13 maja 1994 r., po przeżytym I Parafialnym Kongresie Maryjnym. Pierwszy Parafialny Kongres Maryjny, którego hasłem było: „Abym była więcej znana i miłowana”, trwał od 6 do 12 maja i był wielkim wydarzeniem z bardzo bogatym programem, który wypełniał wiele godzin każdego dnia. Kongres ten zaowocował tym, że do życia w parafii zostały powołane: Legion Maryi oraz Bractwo Szkaplerzne, które erygował o. Kamil Maccise OCD, przełożony generalny.
Oprócz Bractwa Szkaplerznego i Legionu Maryi istnieje 16 Róż Żywego Różańca, Apostolstwo Dobrej Śmierci, Ruch Szensztacki, Domowy Kościół, Grupa modlitewna św. Ojca Pio, Czciciele Miłosierdzia Bożego „Faustinum” i Rycerstwo Niepokalanej.
W ciągu roku – od 14 października 1995 r. do 11 października 1996 r. – parafie naszej Ojczyzny nawiedzała Maryja w znaku Pielgrzymującej Figury z Fatimy. Podczas peregrynacji nawiedziła Maryja i nas 21 czerwca 1996 r., a odjeżdżając do Fatimy pozostawiła prezent w postaci pozwolenia udzielonego przez Władze Miejskie dla parafii na budowę Domu Parafialnego i świątyni. Budowę Domu Parafialnego rozpoczęto 23 października 1996 r., a zakończono przed świętami Bożego Narodzenia 1999 roku. Budowę kościoła parafialnego rozpoczęto 14 maja 1998 r., a już 13 października w Roku Jubileuszowym ks. abp Henryk Muszyński mógł wmurować kamień węgielny. Parafia otrzymała go 10 czerwca 1995 r. w postaci marmurowej płyty, która była częścią ołtarza głównego z Bazyliki w Fatimie. Poświęcił go dwa lata później, 3 czerwca 1997 roku, Jan Paweł II podczas VI Wizyty Apostolskiej do Ojczyzny w Prymasowskiej Bazylice w Gnieźnie.
Dnia 24 lutego 2004 r. Nuncjusz Apostolski ks. abp Józef Kowalczyk ogłosił komunikat, że Ojciec Święty Jan Paweł II, w duchu pasterskiej troski o Kościół, który jest w Polsce, realizując założenia bulli Totus Tuus Poloniae populus ustanowił z dniem 25 marca – w Uroczystość Zwiastowania Pańskiego, diecezję bydgoską, a ks. bp. Jana Tyrawę dotychczasowego biskupa pomocniczego w archidiecezji wrocławskiej – biskupem bydgoskim. Nowy Biskup Ordynariusz 25 grudnia 2005 r. dokonał poświęcenia nowej świątyni na bydgoskich Wyżynach.
Po poświęceniu świątyni parafia wzbogaciła się o kolejne figury: św. Piotra – pierwszego papieża, Jana Pawła II, św. Ojca Pio, stacje Drogi Krzyżowej – odlane w brązie oraz piękne witraże. Przedstawiają one: objawienia maryjne zatwierdzone przez Kościół, sceny tajemnic różańcowych, sylwetki papieży fatimskich oraz dzieci – Hiacyntę, Łucję i Franciszka a także cud wirującego słońce.
Zamontowane zostały w kościele organy elektro-pneumatyczne przez firmę organową Mariana Majchera, aby poprzez ich 35-głosowy instrument, nie tylko ubogacać liturgię, lecz także ukazywać piękno muzyki organowej.
Obok zaś świątyni powstał ogród różańcowy z dwudziestoma stacjami różańcowymi, w którym znajduje się ołtarz polowy na łodzi przycumowany do dwóch kolumn, obrazujący życie religijne Parafii Matki Bożej Fatimskiej w Bydgoszczy.
7 września 2012 r. kard. Stanisław Dziwisz przekazał delegacji parafialnej relikwie kropli krwi bł. Jana Pawła II. Relikwie te zostały uroczyście wprowadzone do świątyni na bydgoskich Wyżynach 22 października, we wspomnienie liturgiczne Jana Pawła II.
8 grudnia 2017 r., w Uroczystość Niepokalanego Poczęcia NMP odbyła się konsekracja naszego kościoła pod przewodnictwem Biskupa Ordynariusza Diecezji Bydgoskiej Jana Tyrawy oraz z udziałem zaproszonych arcybiskupów: abp Jana Romeo Pawłowskiego z Watykanu i abp Tomasza Pety z Kazachstanu oraz licznych kapłanów, gości i parafian. Poświęcenie kościoła miało miejsce w roku setnej rocznicy objawień fatimskich oraz w dwudziestą piątą rocznicę utworzenia parafii. Podczas Mszy Świętej został także odczytany dekret mocą którego nasza Świątynia otrzymała status Sanktuarium.
