Historicky prvá sv. omša na sídlisku Nad jazerom sa slávila 7. októbra 1990. Celebroval ju pán kaplán Jozef Hanobík z farnosti Kráľovnej Pokoja.
22. apríla 1990 Svätý otec Ján Pavol II. v Bratislave posvätil základný kameň pre stavbu kostola na košickom sídlisku Nad jazerom s titulom patrónov – blahoslavených Košických mučeníkov. Pri tej príležitosti vydal Msgr. Ján Sokol, arcibiskup trnavský, metropolita Slovenska, dekrét o posviacke základného kameňa.
Na jar 1991 sa konala výstava návrhov na nový kostol. Spomedzi 21 návrhov zvíťazil projekt Ing. arch. Miloslava Mudrončíka, košického rodáka žijúceho v Bratislave. Jeho návrh upútal predovšetkým maximálnou úsporou plochy a čistým architektonickým riešením:
- Pôdorys samotného kostola je kruhový, pričom jeden kruhový výsek tvorí kaplnka.
- Po oboch stranách kostola sú dvojpodlažné krídla, v ktorých sú sakristie, spovedelnice, farský úrad, učebne, klubovne, dielňa, kotolňa, sociálne zariadenia, garáže a byty kňazov.
- Nosný systém tvorí železobetónový skelet.
- Strecha nad kostolom má oceľovú konštrukciu.
- Jej hlavnými nosnými prvkami sú 4 oceľové väzníky spojené do svorníka a tie v pôdoryse tvoria kríž.
- Objekt kostola je založený na pilótach.
- Interiér kostola a dispozícia kruhu vytvára úzky kontakt medzi veriacimi a kňazom.
- Kostol má ústredné kúrenie a elektrické osvetlenie.
S platnosťou od 1. júla 1991 diecézny biskup Msgr. Alojz Tkáč vyčlenil sídlisko Nad jazerom spod Farnosti Kráľovnej Pokoja – Košice Juh a zriadil novú Farnosť Košice – Nad jazerom. K farnosti pričlenil aj filiálku Vyšné Opátske.
Na sviatok narodenia Panny Márie 8.septembra 1991 posvätil otec biskup Alojz Tkáč pozemok na výstavbu kostola. Pod holým nebom sa zhromaždili veriaci, kňazi, bohoslovci, rehoľníci aj zástupcovia verejnej správy.
Prvé práce na pozemku sa začali na jeseň roku 1991.
Skutočne prvá sv. omša v novostavbe kostola, hoci ešte nie celkom dokončeného, sa na prosbu farskej rady a s dovolením biskupstva konala na Vianoce 1994 o polnoci. Celebroval ju pomocný biskup Msgr. Bernard Bober za účasti asi 3000 ľudí.
Kostol Košických mučeníkov bol dokončený a slávnostne konsekrovaný 25. júna 1995. Učinil tak arcibiskup – metropolita Msgr. Alojz Tkáč. Celá vysviacka kostola sa niesla v duchu motta: Postavia mi svätyňu, a budem bývať uprostred nich.” (Ex. 25,8).
Čoskoro po svätorečení sa do chrámu dostal obraz košických mučeníkov, ktorý má okrem umeleckej hodnoty aj hodnotu historickú. Slúžil totiž ako hlavný oltárny obraz pri omši pápeža Jána Pavla II. na košickom letisku dňa 2. júla 1995.
Po svätorečení boli do kostola donesené aj relikvie svätých Košických mučeníkov, ktoré boli na svätorečenie donesené z Trnavy.
Základné technické údaje o kostole a pastoračnom centre:
- výška: 24 m
- polomer: 15,4 m
- priemer: 31 m
- šírka, dĺžka: 47 m x 47 m
- kapacita kostola: 1600 miest
- kapacita kaplnky: 400 miest
Kúrenie kostola je podlahové, kaplnka a ostatné objekty sú vykurované cez radiátory. Energetickým zdrojom je plyn a celý objekt má vlastnú plynovú kotolňu.
Celkové náklady na stavbu kostola boli 32 100 000 Sk. Z toho 14 000 000 Sk boli zbierky vo farnosti a svojpomocné práce, 7 000 000 Sk boli zbierky zo Slovenska, ostatné financie boli darom tak zo zahraničia, ako aj zo Slovenska.