Zwraca uwagę jego architektura w stylu bizantyjskim, co nie powinno dziwić, albowiem jest to dawna cerkiew z roku 1902. W okresie międzywojennym świątynię odremontowano i przystosowano do liturgii rzymskokatolickiej przeznaczając ją na kościół garnizonowy pod wezwaniem Matki Bożej Królowej Polski. Gdy w roku 1901 kielczanie zaczęli wznosić kościół św. Krzyża, władze gubernialne postanowiły postawić w mieście drugą cerkiew dla stacjonującego w mieście garnizonu rosyjskiego. Jej architekturę wzorowano na sławnym petersburskim soborze izaakiewskim.
Wzniesiona na planie krzyża greckiego (równoramiennego) budowla, nakryta jest okazałą, centralną kopułą.
W roku 1925 została przekazana katolickiemu duszpasterstwu wojskowemu i po remoncie erygowana jako parafia wojskowa. Wyposażenie wnętrza pochodzi głównie z 1926 roku. W kościele wmurowane są tablice poświęcone żołnierzom i partyzantom poległym w obronie Ojczyzny.