
První kostel v Lešné byl postaven v l. 1420–1430. Kostel, který byl dřevěný, byl postaven za Hanuše z Pržného. Od r. 1605 sloužili v kostele luteránští kněží. R. 1621 vypálilo Lešnou i s kostelem a částí zámku vojsko, které bylo do obce vysláno pro připojení vrchnosti k odboji proti panovníkovi Ferdinandu II. R. 1628 koupil panství Martin Půhočí z Předmostí, za kterého byl v l. 1628–1635 postaven nový kostel, opět z větší části dřevěný. Původně byl kostel zasvěcen Blahoslavené Trojici.
V l. 1684–1686 nechal Jan Emanuel hrabě Lažanský, nový majitel panství, kostel, který byl ve špatném stavu, celý přestavět, tentokrát již byla stavba zděná – byly přistavěny dvě kaple a kostel dostal tvar kříže. V l. 1726–1728 byla přistavěna věž s cibulovitou střechou. Duchovní správa byla obnovena r. 1730, novým duchovním správcem se stal p. Max Prechlý. R. 1732 byly do věže kostela zavěšeny tři zvony – sv. Michaela (1000 kg), sv. Jana (560 kg) a sv. Valentina (261 kg) a kostel byl stavebně upraven – nová klenba, dvě nové oratoře, interiér vyzdobil freskami známý moravský barokní malíř Josef Ignác Sattler (1725–1767). Kostel byl poté nově zasvěcen sv. Michaelovi Archandělovi. Varhany v kostele jsou z r. 1885.
Za 2. sv. války byly zrekvírovány zvony sv. Jana a sv. Valentýna a malý umíráček.
R. 1969 byl zvon sv. Michaela prohlášen národní kulturní památkou, r. 1972 byl mezi národní kulturní památky zařazen celý kostel.