Kostel je nejstarší stavební památkou na území města Karviné. Výstavba se datuje k r. 1327 a je spojená s vládou Meška I. z rodu Piastovců. Nejstarší písemná zmínka o kostele pochází z r. 1376. Jedná se o původní kamennou jednolodní gotickou stavbu s půdorysem latinského kříže, později renesančně a barokně upravenou. Chrámová loď je 38 metrů dlouhá a příčná loď 34 metrů široká. Dispozice latinského kříže byla nejspíš inspirována kostely sv. Kříže a Bartoloměje ve Vratislavi a klášterním kostelem dominikánů v Těšíně (r. 1300). Pod kostelem a kaplemi se nachází nepřístupná krypta několika hrobek. Tato stavba se nachází v blízkosti Fryštátského zámku a zámecké zahrady. Od roku 1958 je chráněna jako kulturní památka České republiky.

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. Po značné rekonstrukci byla vystavěna v letech 1515–1530 zděná věž se čtyřmi zvony.

V letech 1611–1617 byla ke kostelu přistavěna Moravské kaple, později kaple sv. Jana Nepomuckého.

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í.

Ke konci 18. století byl kostel značně poškozen požárem. V 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ží 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. Malby znázorňují umučení sv. Kateřiny a sv. Barbory. Soubor výjevů ze života sv. Kateřiny je pak dokonce nejstarším dochovaným freskovým příběhem této světice v České Republice. „Malby zachycují dva cykly ze života dvou světic. Znázorňují obrácení sv. Kateřiny a sv. Barbory na křesťanskou víru. Autor ztvárnil jejich mučení. Například řezání prsou, vláčení pod kopyty koní až jejich popravu. Zajímavé je, že v případě Barbory mučení prováděl přímo její otec.“