Dnia 1 stycznia 1933 r. dekretem Ks. Bp. Stanisława Wojciecha Okoniewskiego, Ordynariusza dawnej diecezji Chełmińskiej powołano do istnienia samodzielną placówkę duszpasterską jako tzw. „kurację” pw. Podwyższenia Krzyża Św. Pierwszym administratorem został ks. Józef Mówiński, zamordowany później przez hitlerowców w lasach Piaśnicy. Na Witominie funkcjonował już drewniany barakowy kościół, który przetrwał do roku 1945. Pod koniec wojny kościół ten został spalony w wyniku działań wojennych. Mieszkańcy Gdyni Witomina, po tym smutnym fakcie uczęszczali do kościoła w Małym Kacku i równocześnie budowali nowy kościół na miejscu starego – spalonego. 8 grudnia 1947 r. Ks. Biskup Kazimierz Józef Kowalski, Ordynariusz diecezji Chełmińskiej poświęcił nowobudowany kościół, który stoi do dziś. Wówczas kościół otrzymał drugi tytuł: Niepokalanego Poczęcia Najświętszej Maryi Panny. Kolejnymi proboszczami na przestrzeni lat byli: Ks. Paweł Lubiński, Ks. Robert Rompa, Ks. Lucjan Dambek i Ks. Władysław Szulta, Ks. Zygfryd Leżański, ks. Tadeusz Balicki, a obecnie ks. Piotr Szamocki. W latach 90-ch parafia wybudowała nowy Dom Parafialny. W pierwotnych zamierzeniach miał to być bardzo potrzebny, wręcz konieczny Dom Katechetyczny.
Dzisiaj ów Dom Parafialny stanowi zaplecze duszpasterskie, bez którego byłoby trudno pracować, mając na względzie różne stowarzyszenia katolickie, ruchy i grupy parafialne. Tym bardziej, że sam kościół jest ciągle za mały. Brakowało w nim miejsca dla wiernych wcześniej, kiedy nie było jeszcze podziału na dwie kolejne parafie i nie ma go dzisiaj, gdyż Witomino jako jedna z najpiękniejszych dzielnic Gdyni ciągle się rozbudowuje. Na początku Trzeciego Tysiąclecia Chrześcijaństwa parafia , przy wydatnej pomocy licznych mieszkańców Gdyni postawiła w roku 2000 / 2002 monumentalnych rozmiarów pomnik Matki Bożej Gdyńskiej, który jest posadowiony na Skwerze Ks. Józefa Mówińskiego.
Obecnie macierzysta Parafia na Witominie podejmuje trud rozbudowy swego kościoła.