Od raného středověku stávala vysoko nad Vítochovem svatyně, kterou nechal údajně založit sv. Metoděj. Řadí se tak k nejstarším památkám na Moravě. Románsko-gotický vzhled se zbytky hradeb a baštou připomíná časy, kdy by kostelík zároveň i pevností.  

Vítochovský kostelík je jeden z nejstarších kostelů na Moravě. Říká se, že na místě, kde dnes svatostánek stojí, kdysi bývalo pohanské pohřebiště. I pod podlahou kostela bylo nalezeno několik desítek lidských koster. Odborníci odhadují, že mohou patřit obětem třicetileté války. Tehdy do vsi přitáhli Švédové, ale vesničané se před nimi ukryli v opevněném kostelíku. Nesoucitní vojáci však kostel i s místními obyvateli zapálili. K nejstarším památkám interiéru kostela patří gotické fresky.  Výjevy zobrazují Vjezd do Jeruzaléma, Poslední večeři Páně, Ježíšovo umučení a zmrtvýchvstání i výjevy z Kristových pašijí. Najdete zde také malby Panny Marie a archanděla Michaela, kterému je kostelík zasvěcen.

Podle legendy tudy za Velké Moravy procházel sv. Metoděj. Pán z Vítochova ho srdečně přivítal a přijal i křesťanskou víru. Před Metodějovým odchodem slíbil, že na památku jeho návštěvy nechá vystavět kapli a svůj slib brzy skutečně dodržel. Za čas Metoděj znovu do těchto končin přijel, a jakmile spatřil kostelík, vzpomněl na slib, který mu tehdy vítochovský pán dal, a kostelík slavnostně vysvětil. Traduje se, že dodnes dochovaný mramorový oltář a křtitelnice pocházejí právě z těchto časů a svatého Metoděje tedy pamatují.