Při zakládání města Fryštát v r. 1303–1306 těšínským knížetem Meškem I. jako správním a tržním střediskem severozápadní části těšínského vévodství již byl v plánech určen prostor pro farní kostel. Není jasné, jestli stavba kostela byla financována dobročinností bohatého jedince nebo sbírkou celé obce. První zmínky o tomto kostele pochází z r. 1376, kdy byl knížetem Přemyslem I. Těšínským a farářem Janem rozšířen o nadaci oltáře Božího Těla a sv. Jana Evangelisty. Oltáře byly umístěny do postranní presbytáře. Dobu vzniku tohoto oltáře však nelze přímo určit. Z této listiny plyne, že ještě před založením tohoto oltáře zde stál mimo hlavního i jiný oltář, což svědčí i o dřívější stavbě toho kostela (v pramenech se uvádí 1327). Nedochovaly se však žádné spisy dokazující velikost majetku kostela či jeho farnosti. Kult Božího těla byl v povodí Odry ve 14. století značně rozšířený. Již v roce 1349 byl založen oltář tohoto kultu v Hlubčicích dále pak v Ratiboři a v Hlučíně, z čehož lze soudit, že vznik vedlejšího oltáře Božího těla a sv. Jana Evangelisty spadá do poloviny až třetí čtvrtiny 14. století.

V roce 1420 byla Petrem Hobergem sepsána fundační listina potvrzující stavbu kaple zasvěcenou Panně Marii s oltářem Všemohoucího Boha, Stanislava a svatých Alžběty, Anny, Doroty, Hedviky, Kateřiny a Markéty. Kaple byla postavena jako reakce na husitské povstání ve Slezsku. Nelze však určit, kde přesně tato kaple stála a zda nešlo o samostatný stavební útvar.

Do 15. století byl kostel bez věže. Ta stála do té doby jako samotná dřevěná stavba vedle kostela, avšak v roce 1511 došlo ve Fryštátě k velkému požáru, který způsobil škody i na kostele (potvrzují dochované listiny původního kostelního majetku). Po značné rekonstrukci byla vystavěna v letech 1515–1530 zděná věž se čtyřmi zvony (Julius Bayer uvádí šest zvonů) mezi severním transeptem a západní části hlavní lodi. K věži bylo přistavěno vnější točité schodiště s věžičkou ze západní strany kostela sahající až do třetího patra věže. Kostel také pošel přestavbou stropní konstrukce z trámové na lomenou. V dochovaných zprávách z roku 1521 je uveden uprostřed kostela pilíř z čehož můžeme soudit, že byl kostel dvoulodní. To dosvědčují i původní dochované dva lomené oblouky stropní konstrukce lodí v podkroví kostela.

Ve výsledku jsou ze středověkých zpráv uvedeny k původnímu kostelu zasvěcenému Panně Marii další čtyři boční oltáře: oltář Božího těla a sv. Jana Evangelisty, oltář sv. Kříže (jižní rameno transeptu), oltář Všemohoucího Boha a oltář Všech Svatých. V kapli Matky Boží (severní transept) byl umístěn obraz matky Boží v oltáři. Nachází se zde také zazděná hrobka určená k pohřbívání rodiny pána z Cikánů.

Výstavba Moravské kaple, později kaple sv. Jana Nepomuckého, byla zahájena v r. 1611 (Julius Bayer 1511) a dokončena v r. 1617. Zdali se jednalo o kapli navazující na původní kapli Panny Marie z r. 1420 není jisté.

V okolí kostela se nacházela řada dalších staveb, kupříkladu špitál vystavěný vévodkyní Annou z konce 15. století, farní budova původně dvoupatrová dřevěná, „deficitní kněžský dům“ určený pro přestárlé kněze, škola, atd. Mezi těmito domy a kostelem se rozprostíral hřbitov pro zasloužilé měšťany. Tento hřbitov byl později zazděn zahradní zdí.

Kostel náležel po celou dobu pánům majitelům fryštátského panství. Ti však přenechávali právo jmenování biskupského pastýře a faráře biskupské stolici.

Ke konci 18. století byl kostel značně poškozen požárem, přičemž musela být stržena střecha a následně přestavěn. Počátkem 19. století byl obraz nad hlavním oltářem „Nanebevzetí Panny Marie“ (gotický styl na dřevě) knížetem biskupem Josefem Kristiánem nahrazen obrazem „sv. Kříže“, a tím byl kostel přejmenován na Povýšení sv. Kříže.

Před výmalbou interiéru v roce 2011 byly objeveny v kapli svaté Matky Boží (severní rameno transeptu) gotické malby zřejmě z 15. století. Po zrestaurování bylo zjištěno, že se jedná o takzvané „secco“ malby nanášené na vápennou omítku. Barvy jsou tvořeny většinou minerálními pigmenty a jejich pojivem byly vaječné bílky, klovatiny, arabské gumy aj.