V místě současného kostela stával kostel již před staletími. Vystavěli jej potomci kolonistů (osídlenců), kteří byli původně z Německa. Proto se také náměstí říkalo Německá Olešnice na rozdíl od Moravské Olešnice, která ležela na pravém břehu Olešnického potoka. Kostelík byl dřevěný a byl postaven v roce 1391.

Okolo něj byl hřbitov. Když krajem táhli husité, aby obléhali hrady protivníků (např. Svojanov, Boskovice) v roce 1424, vypálili prý tento kostelík, a proto byl na jeho místě postaven kamenný gotický kostel vysvěcený na den sv.Vavřince, tj. 10. srpna 1426.

V okolí tohoto kostela se pohřbívalo až do poloviny l8.století, kdy byl hřbitov zrušen, (poslední pohřeb se zde konal v r. 1784). Přestože stavba přečkala staletí, neodolala nejničivějšímu požáru v Olešnici v červenci 1827.

Bylo rozhodnuto na jeho místě postavit nový. Ten byl postaven v letech 1831-1839 nákladem majitele panství a zasvěcen na počest jeho manželky Leopoldiny, svobodné paní z Honrichsu, sv. Leopoldu. Změnou původního vzhledu bylo postavení nové střechy na věži kostela v roce 1882. Věž do té doby měla pouze nízkou trojúhelníkovou střechu. V roce 1943 byl kostel znovu vysvěcen na kostel sv. Vavřince.

Při stavbě opěrné zdi v roce 1938 proti radnici bylo nalezeno mnoho kosterních pozůstatků ze zrušeného hřbitova. Při rekonstrukci náměstí v roce 1998 a pak v roce 2003 byla při budování kanalizace u severní strany kostela odkryta v hloubce cca 1,5 metru kostnice. Po církevním obřadu byly ostatky uloženy na hřbitově na Moravské straně u kostela sv. Mikuláše.

Římskokatolická farnost v Olešnici provedla nákladnou výměnu střechy věže kostela a rekonstrukci fasády v roce 2004, a tak je tato kulturní památka objektem, který náměstí dominuje i pěkným vzhledem.