Počátkem 20.století vyvolal růst počtu obyvatel na brněnských předměstích potřebu stavby nových kostelů. Židenice nebyly výjimkou. V roce 1910 se na podnět tehdejšího katechety v Židenicích P.F.Hudce ustavil „Spolek pro stavbu katolického chrámu v Židenicích-Juliánově“ s cílem postavit kostel a zřídit samostatnou farnost. Spolek ve třech letech získal přes 1300 členů a již roku 1911 zakoupil za 95.000 Kčs komplex pozemků (tzv. Melionky) o rozloze 29.810 m2­. V roce 1914 dal vypracovat od architekta Vladimíra Fischera náčrtek stavby budoucího chrámu, ale pro první světovou válku byla stavba oddálena.
Dne 28.října 1928 byl posvěcen základní kámen budoucího kostela. V soutěži řešení byl vyhodnocen jako nejlepší návrh architekta Klaudia Madlmayra a v roce 1932 byla započata stavba kostela podle jeho plánů. Kostel byl posvěcen dne 27.října 1935 brněnským biskupem Dr.Josefem Kupkou.
Projektant Klaudius Madlmayr pojal stavbu jako trojlodní baziliku. Je orientována přibližně ve směru východ – západ s hlavním vstupem v západním průčelí. Hranolovitá věž (vysoká 46 metrů) s osmibokým nástavcem přiléhá k severní straně kostela.Nad arkádovým podloubím kryjícím vstup do kostela je centrálně umístěn čtvercový reliéf sv.Cyrila a Metoděje.
Hlavní loď je dlouhá 33 m, široká 11,5 m a vysoká 16 m. Boční lodi jsou 4 m široké a 6,5 m vysoké. Kněžiště, které uzavírá apsida zaklenutá báňovou klenbou, obklopují z vnější strany sakristie, křestní kaple a depozitáře, v patře pak oratoře. V zadní části kostela, v prostoru pod věží, je kaple. Kostel pojme 1200 věřících, z toho 250 má možnost sedět v lavicích.
Vnitřní výtvarné řešení se provádělo postupně podle finančních možností. Na výzdobě a vybavení kostela se podíleli mj. bratři Heřman a Karel Kotrbovi, Petr Pištělka, Ludvík Kolek, Julius Pelikán, Václav Andres, Jan Vasilij Čermák a Karel Stádník.
Po dostavbě kostela a jeho vysvěcení byli duchovní správou pověřeni premonstráti, tehdy působící ve farnosti Brno-Zábrdovice, která byla „domovskou“ farností i pro Židenice. Samostatná farnost v Brně-Židenicích byla zřízena k 1. lednu 1953 a duchovní správou byli pověřeni diecézní kněží.

Betlém
Betlém v kostele sv. Cyrila a Metoděje v Brně-Židenicích pochází z roku 1938. Jeho autorem je malíř a řezbář Václav Andres,který vystudoval na pražské Akademii výtvarných umění u profesora Hynaise. Postavy betléma jsou přibližně 40 cm vysoké. Betlém je každoročně stavěn v kapli Panny Marie Bolestné, která se nachází v levé lodi kostela.
Kromě tohoto betlému bývá od roku 2008 vystaven bílou polevou zdobený perníkový betlém paní Vlasty Šimoníkové, který je se svými 1215 figurkami zapsán v Guinesově kniza rekordů.