Kapucíni přišli do Brna v roce 1604 na pozvání olomouckého biskupa Františka z Ditrichštejna. Pro svůj první klášter si vybrali místo na východním předměstí, kterému se říkalo Před Měnínskou branou, a na jaře téhož roku položili základní kámen. Kostel svatého Františka z Assisi v roce 1606 vysvětil samotný kardinál Ditrichštejn. Na jeho výzdobě se podílel vynikající malíř Kosmas z Castelfranca, kněz benátské provincie, který tvořil nejen pro vznikající kapucínské kostely, ale také pro císaře Rudolfa II.
Na konci třicetileté války, když Brno obléhali Švédové, však kapucíni o svůj klášter přišli. Vojenský velitel města Raduit de Souches totiž nařídil srovnat se zemí všechny domy před hradbami, aby si v nich švédská vojska nemohla najít oporu. V březnu 1645 byl kapucínský klášter zbořen. Bratři našli azyl nejdříve na staré radnici, později bydleli v měšťanském domě vedle Biskupského dvora.

Pro svůj druhý klášter si kapucíni vybrali místo na Uhelném trhu, dnešním Kapucínském náměstí. Stavba trvala plných osm let (1648–1656). Pozemek pro nový kostel daroval hrabě František Magnis, rodný bratr kapucínského diplomata Valeriána Magniho. Stály na něm tři domy, které byly posléze zbořeny. Pro stavbu kláštera bylo postupně vykoupeno dalších šest domů v sousedství. Peníze na stavbu kapucíni získali od dobrodinců, mezi největší patřil moravský zemský hejtman Kryštof Pavel z Lichtenštejna-Kastelkornu a Ferdinand Mencl z Kolsdorfu, přísedící královského tribunálu v Brně. Druhý kapucínský kostel byl slavnostně vysvěcen 7. května 1656 olomouckým světícím biskupem Janem Gobbarem. Už však po šesti letech bylo nutné snést jeho cihlovou klenbu kvůli špatně postaveným zdem a nepevným základům. Na dalších téměř sto let ji nahradil plochý dřevěný strop.
Během 18. století prošel areál kláštera pod vedením brněnských stavitelů a architektů Mořice Grimma a později jeho syna Františka Antonína výraznými stavebními změnami, které se týkaly i kostela. Roku 1753 byla vedle kaple sv. Františka přistavěna kaple sv. Fidela a celý kostel získal nový klenutý strop. V roce 1747 byla v souvislosti s oslavami svatořečení Fidela ze Sigmaringen a Josefa z Leonessy vystavěna kruchta a o rok později už mše svaté doprovázely první pevné varhany.
Druhá velká vlna změn spadá do 20. století, mezi dvě světové války. Kostel získal nové varhany poháněné elektřinou, kvůli kterým musela být kruchta rozšířena o přední oblouk. Jejich design napodobuje barokní a renesanční prvky. Rovněž část vitráží v secesním stylu pochází z 20.let minulého století; jejich autora však neznáme. Mladší vitráže, z 30. let, patrně vytvořila brněnská dílna Jiřího Říhy.
V roce 2012 prošel interiér kostela rozsáhlou rekonstrukcí, vedle nového osvětlení a šetrnějšího vytápění se mu dostalo i kompletní výmalby. V letech 2014–2017 následovala oprava fasády a v roce 2015 náročná oprava varhan.

Exteriér kostela
Kostel je postaven v jednoduchém barokním slohu, v souladu s pravidly kapucínského řádu, který je ovlivněn návratem k původním ideálům chudoby. Neorientovaná stavba stojí zhruba ve směru vrstevnice v mírném svahu, jenž se zvedá k Petrovu. Před kostelem je zbudovaná opěrná zeď se třinácti schody směřujícími k hlavnímu vchodu. Nad portálem se nachází mozaika svatého Františka z Assisi, jak káže ptákům. Původní freska Nalezení svatého Kříže byla zničena povětrnostními vlivy.
V roce 1765 pak zkrášlily terasu před vstupem do kostela sochy františkánských a kapucínských světců od brněnského umělce Jana Adama Nessmanna, zleva Josef z Leonessy, Fidel ze Sigmaringen, František z Assisi, Antonín z Padovy a Felix z Cantalice. Postava svatého Vavřince z Brindisi od českého sochaře Čeňka Vosmíka doplnila tuto pětici až v roce 1927.

Interiér kostela
Hlavní oltářní obraz zachycuje svatou Helenu v císařském rouchu nad právě nalezeným Kristovým křížem a vzkříšení mrtvé ženy, která se jej dotýká, čímž potvrzuje jeho pravost. Obraz v roce 1655 namaloval německý malíř a spisovatel Joachim von Sandrart a patří k nejvýznamnějším barokním oltářním malbám v Brně. V roce 2016 byl obraz kompletně restaurován akademickým malířem Igorem Fogašem.
Příčinou, proč kapucíni svůj chrám zasvětili právě události nalezení svatého Kříže, je pravděpodobně mimořádný dar kněžny Polyxeny z Lobkovic. Tato velmi štědrá dobrodinkyně totiž bratřím v roce 1636 věnovala ostatky onoho kříže z Golgoty, které se v klášteře dodnes uchovávají ve stříbrné schránce, uvnitř zdobené výšivkou a říčními perlami.
Po stranách se nacházejí úzké obrazy dvou řádových světců Fidelia ze Sigmaringen a Josefa z Leonessy. Díla pocházejí z poloviny 18. století a stejně jako u dalších obrazů v kostele je jejich autorství sporné, snad šlo o řádového malíře. Pod nimi, v místech vchodů do chóru bratří, jsou vsazeny dva obrazy andělů Posledního soudu a Anděla strážce z konce 17.století.
Součástí presbytáře je také dvojice oltářů sv. Josefa a sv. Antonína Paduánského. V bočních kaplích jsou na oltářních obrazech výjevy Stigmatizace sv. Františka z Assisi a Apoteóza sv. Fidelia ze Sigmaringen. Na epištolní straně se nachází poslední oltář, zasvěcený prvnímu svatořečenému kapucínovi Felixi z Cantalice. Oltář vysvěcený roku 1714 byl podle erbu fundován hrabětem Karlem Ludvíkem z Rogendorffu.
Na bočním oltáři svatého Fidela se nachází obraz Panny Marie Pasovské. Velmi pravděpodobně jde o dílo, jež kapucínská kronika zmiňuje jako „zázračný obraz“. Váže se k němu totiž legenda o zázračné pomoci, které se mělo dostat na přímluvu Matky Boží majiteli obrazu, císařskému radovi Františku Antonínu de Cattani. Před svou smrtí jej odkázal bratřím kapucínům, aby byl v kostele vystaven veřejné úctě. Obraz je věrnou kopií slavného díla Lucase Cranacha staršího (zřejmě z roku 1641); originál (1537) se nachází v katedrále v rakouském Innsbrucku. Předtím byl určitou dobu umístěn v kostele v bavorském Pasově, odtud P. Marie Pasovská.

Betlém
Historie: V roce 1955 dostal brněnský sochař a restaurátor Jaroslav Vaněk k dispozici prostor v zadní části chrámové lodi kapucínského kostela s prosbou o vytvoření betléma. Sochař, kterému byl určen pouze prostor bez jakýchkoliv dalších požadavků, zde vytvořil pozoruhodné dílo, kde ve výrazu obličeje každé postavy můžeme vyčíst určité pohnutí – zadumání, úžas či překvapení. Za svého života stavěl tento betlém autor vždy sám, naposledy v roce 1990. Tehdy se zrodil nápad umístit mezi figurky betléma také postavu Sv. Františka z Assisi coby zakladatele tradice stavění jesliček. V létě roku 1991 J.Vaněk vyřezal své poslední dílo – reliéf sv. Františka – jako součást betléma v kostele u kapucínů. Ve stejném roce 4.října, v den svátku tohoto světce, J. Vaněk zemřel. Sv. František je v jeho betlémě zpracován podle motivu z příběhu o vlku z města Gubia. Figuru vlka, které sochař nestihl vyřezat hlavu, dokončil později jeho spolupracovník pan Kokeš.
Popis: Střed betléma je tvořen chýší s figurami Svaté rodiny. Maria ukládá narozeného Ježíška do jesliček a nad nimi se sklání sv. Josef. Kromě tří králů, přinášejících dary, jsou zde figury pastýřů s ovečkami. Vlevo v pozadí jsou dva reliéfy, zobrazující klanění pastýřů, a dále anděla, který jim oznamuje narození Krista. Na reliéfu vpravo je zobrazen svatý František z Assisi s vlkem.