Kościół ten jest najstarszym zabytkiem budowlanym na terenie Karwiny. Budynek jest datowany na 1327 r. i wiąże się z okresem władzy Mieszka I z dynastii Piastów. Najstarszy zapis o kościele pochodzi z 1376 r. Jest to oryginalny jednonawowy obiekt gotycki na planie krzyża łacińskiego, poddany w późniejszych okresach przebudowom renesansowym i barokowym. Nawa kościoła ma długość 38 m, nawa poprzeczna ma szerokość 34 m. Dyspozycja krzyża łacińskiego była prawdopodobnie zainspirowana kościołami Krzyża Świętego i św. Bartłomieja we Wrocławiu oraz kościołem klasztornym dominikanów w Cieszynie (1300 r.). Pod kościołem i kaplicami znajduje się niedostępna krypta zawierająca kilka grobowców. Obiekt znajduje się w pobliżu Zamku Frysztackiego i ogrodu zamkowego. Od 1958 r. jest objęty ochroną jako zabytek kultury Republiki Czeskiej.

Do XV w. nie posiadał wieży. Drewniana wieża stała do tego czasu samodzielnie obok kościoła, jednak w 1511 r. w Frysztacie wybuchł wielki pożar, który uszkodził także kościół. Po znacznej odbudowie wzniesiono w latach 1515–1530 murowaną wieżę z czterema dzwonami.

W latach 1611–1617 dobudowano do kościoła Kaplicę Morawską, później kaplicę pw. św. Jana Nepomucena.

Wokół kościoła znajdowało się wiele innych budynków, na przykład szpital ufundowany przez księżnę Annę z końca XV w., budynek parafii, pierwotnie dwukondygnacyjny, drewniany, „deficytowy dom księży” przeznaczony dla starych księży, szkoła itd. Pomiędzy wyżej wymienionymi obiektami a kościołem leżał cmentarz dla zasłużonych mieszczan. Cmentarz został w później zamurowany murem ogrodowym.

Pod koniec XVIII w. kościół uszkodził w znacznym stopniu pożar. W XIX w. książę - biskup Josef Kristián zastąpił obraz „Wniebowzięcia Najświętszej Maryi Panny” nad głównym ołtarzem (wykonany na drewnie, w stylu gotyckim) obrazem „Krzyża Świętego”, wskutek czego kościół został przemianowany na kościół Podwyższenia Krzyża Świętego.

Przed malowaniem wnętrz w 2011 r. w kaplicy Matki Bożej odkryto gotyckie malowidła z XV wieku. Po renowacji ustalono, że były to tak zwane malowidła „secco” wykonywane na wapiennym tynku. Farby były tworzone głównie pigmentami mineralnymi, a ich spoiwem były białka jajeczne, gumy naturalne, gumy arabskie i inne substancje. Malowidła przedstawiają męczeństwo św. Katarzyny i św. Barbary. Zbiór scen z życia św. Katarzyny jest w dodatku najstarszą w Czechach zachowaną historią tej świętej wykonaną na fresku. „Malowidła przedstawiają dwa cykle z życia dwóch świętych. Przedstawiają nawrócenie św. Katarzyny i św. Barbary na wiarę chrześcijańską. Autor namalował ich tortury. Na przykład obcięcie piersi, rzucenie pod kopyta koni i ich stracenie. Je zadziwiające, że Barbara była torturowana bezpośrednio przez swego ojca.”