Původní kostel zřejmě dřevěný byl postaven ve Vranově jako vděk za uzdravení Viléma moravského zemského maršála. V kostele byla umístěna soška Panny Marie z lipového dřeva. V letech 1617-1633 byl vystavěn dnešní nový monumentální chrám, iniciátor byl Maxmilián z Lichtensteina. Současně s tím byl v letech 1626-1633 při chrámu vystavěn klášter pro řád Nejmenších bratří sv. Františka z Pauly – paulánů. Za josefínských reforem byl klášter zrušen a zčásti pobořen. Z jeho cihel byla postavena kasárna v Brně-Cejlu. V roce 1992 se konal návrat paulánů, kteří zde budují duchovní centrum.

Jednolodní barokní kostel s klasicizujícími prvky doplňují dvě věže. Interiér zdobí několik uměleckých děl od různých autorů a kostelní klenbu freska od Jana Jiřího Etgense. Hlavní oltář zdobí obraz Nejsvětější Trojice od malíře P. Trogera a soška Panny Marie Vranovské od neznámého francouzského řezbáře z počátku 16. století. Pod kostelem se nachází krypta rodu Lichtensteinů. Kromě zhruba 50 pochovaných členů rodu jsou zde i umístěna balzamovaná srdce manželek, které kvůli svému původu nemohly být pochovány vedle svých manželů.