Počátky kostela Narození Panny Marie ve Starém Bohumíně, nejstarší kulturní památky na území Bohumína, jehož duchovními správci byli kolem poloviny 13. století benediktýni, zůstávají kvůli nedochovaným historickým záznamům zahaleny tajemstvím. Zdejší klášterní komunitu údajně tvořili probošt a šest dalších řádových bratří z domovského kláštera Týnec u Krakova v Polsku. První dřevěná kaple zde snad stávala již na přelomu 12. a 13. století. Gotickým zděným kostelem byla nahrazena nejspíše již mezi lety 1320 až 1400.

Po smrti posledního ratibořského knížete Valentina z rodu Přemyslovců v roce 1521 a opolského knížete Jana z rodu Piastovců v roce 1523 získal bohumínské panství zástavou do svého vlastnictví krnovský kníže Jiří z ansbašské větve Hohenzollernů. Záhy jej daroval synovi Georgu Friedrichu Hohenzollernovi. Příslušníci tohoto rodu se zanedlouho začali přiklánět místo ke katolictví k protestantismu augsburského vyznání. Jejich dědicové byli braniborští kurfiřti, kteří tíhli pro změnu ke kalvinismu a místní obyvatelstvo podle zásady „čí země, toho víra“ bylo „přinucováno“ k přijetí víry své nové vrchnosti.

Bohumínský kostel byl benediktýnům údajně již v roce 1530 odebrán a svěřen do péče protestantských pastorů augsburského vyznání. Nápisy, které umístili na stěny bohumínského kostela benediktýni, byly odstraněny až téměř o sto let později na základě nařízení těšínského knížete Václava Adama.

Jediný doposud známý protestantský pastor Jiří Floderus z Fryštátu, byl v Bohumíně připomínán v roce 1620 v souvislosti s dokončenou rozsáhlou renesanční přestavbou kostela. Do nově postavené kostelní věže pořídil dva zvony (Adama a Josefa) s velkým obsahem stříbra, zhotovené v opavské zvonařské dílně Hanse Knauffa (zkonfiskované k válečným účelům v roce 1942, ale roku 2014 navrácené).

K pozvolnému návratu ke katolicismu docházelo teprve od roku 1621 po porážce žoldnéřského vojska Johanna Georga Krnovského, syna krnovského knížete a braniborského kurfiřta Joachima Friedricha. Tehdy totiž císař Ferdinand II., který 22. ledna 1621 definitivně zbavil odbojného krnovského knížete bohumínského a bytomského panství, potvrdil zástavní právo na Bohumín a Bytom ze 17. května 1618 pražskému bankéři Lazaru II. Henckelovi z Donnersmarcku a Vösendorfu, hlásícímu se k protestantskému pietismu.

Bohumínský kostel, jehož patronát si nyní vymínil pro sebe samotný panovník, byl protestantům odňat někdy v druhé polovině roku 1629 po odprodeji Bohumína Eliáši Henckelovi. Téhož roku se stal zdejším novým duchovním správcem Jan Fridrichowski.

Když však benediktýnům z Týnce u Krakova byl v restituci navrácen orlovský klášter, dovolil jim vratislavský biskup Karel Ferdinand Waza v roce 1631 převzít právě uvolněné bohumínské farní obročí. To tehdy zahrnovalo osady Bohumín, Dvorek, Gorzyce (PL), Chałupki (PL), Kopytov, Łaziska (PL), Olza (PL), Pudlov, Rudyszwałd (PL), Šunychl, Vrbice a Zabełków (PL). Ekonomické zázemí kláštera, jako například osady Orlová, Lutyně, Rychvald, ale navráceny nebyly. Prvním orlovským opatem sídlícím v Bohumíně se tak stal Athanasius Stanislawski. On a jeho nástupci se ale většinou zdržovali v mateřském klášteře a zde se nechali zastupovat komendáři.

Pro soustavné zanedbávání svých povinností správců bohumínské farnosti jim bylo zdejší farní obročí v roce 1669 odebráno a na uvolněné místo bohumínského faráře, až do příchodu menších bratří františkánů z domovského kláštera v polských Katowicach-Panewnikach v roce 1993, byli jmenováni diecézní kněží. V roce 1668 farníci z přifařených obcí z Olzy, Gorzyc a Łazisk na své náklady přistavěli ke kostelu ze severní strany kapli sv. Jana. Ke změně jejího zasvěcení na kapli sv. Jana Nepomuckého mohlo dojít až po kanonizaci onoho světce, která se uskutečnila 19. března 1729. Několik let poté, nejpozději však v roce 1688, byla přistavěna z jižní strany kaple Panny Marie Růžencové. Půdorys kostela tak nakrátko získal tvar latinského kříže. Do dnešní podoby byla kaple přestavěna v roce 1721. Pod podlahou severní svatojánské kaple byla na náklady majitelů bohumínského panství někdy v této době také zřízena krypta o rozloze cca 20 m2, do níž se pohřbívalo až do druhé poloviny 18. století. Náhrobní kameny pohřbených duchovních a šlechticů, umístěné v podlaze kaple, byly údajně v roce 1900 zakryty novou dlažbou. V noci ze 14. na 15. dubna 1779 byl neznámou zlodějskou bandou vykraden místní kostel tak dokonale, že nic cenného zde nezůstalo. Škoda byla tehdy vyčíslena na neuvěřitelných 1968 rýnských zlatých.

Snad největší škodu utrpěl kostel 22. srpna 1850, kdy do věže kostela uhodil blesk tak nešťastně, že následný požár značně poškodil nejen samotnou věž ze šindele, ale z větší části také krov. Padající trámy prorazily klenbu kostelní lodi. Z kostelního inventáře se podařila zachránit jen malá část. Do roku 1853 byla dokončena oprava střechy a klenby nad kostelní lodí. Původní gotická křížová klenba byla nahrazena klenbou valenou s freskami, čímž z trojlodního kostela vznikl jednolodní. Díky snížení výšky nové klenby kostelní lodi o několik metrů se kružby dvou původních gotických oken dodnes dochovaly na půdě kostela. Rekonstrukce věže, která tehdy ztratila cibulovou báň s lucernou a získala jehlancovou střechu, se uskutečnila teprve až v roce 1854.

Dnešní podobu získal kostel až za rozsáhlé rekonstrukce v letech 1910 až 1911, která se uskutečnila z příkazu c. k. komise pro umění a historické památky. Veškerý novorenesanční mobiliář vyrobila na přelomu 19. a 20. století c. k. umělecká škola dřevařská ve Valašském Meziříčí. Pouze varhany pocházejí z varhanářské dílny bratří Riegrů v Krnově (opus 723 z roku 1899).

V průběhu první světové války byly 17. prosince 1917 pro válečné účely zabaveny dva malé zvony zakoupené Valentinem Josefem Alexandrem a měděný hromosvodový drát. Kostel byl však více poškozen v prvních dvou poválečných letech. Během druhé světové války, kdy byly spolu se zvony (dva z roku 1620 a jeden z roku 1921) pro válečné účely zabavovány i jiné měděné a mosazné předměty, jako například svícny a ministrantské zvonky, byl kostel vážněji poškozen několika granáty, které dopadaly přímo do jeho bezprostřední blízkosti. Válečné škody tak dosáhly výše 42 145 korun.

Díky korunovaci milostného obrazu Panny Marie Růžencové-Starobohumínské, kterou ostravsko-opavský biskup František Václav Lobkowicz vykonal 7. října 2004, byl farnímu kostelu Narození Panny Marie ve Starém Bohumíně navrácen statut lidového poutního místa.