Kostel stál původně uprostřed hřbitova na pravém břehu Bystřičky. Hřbitov zanikl a říčka změnila směr. První písemná zpráva o Bystřici z roku 1368 mluví o městečku, ve kterém byl jistě i farní kostel. Víme, že jeho věž měla cibulovitou podobu (slovanská architektura). Požár roku 1594 ve městě zachvátil také kostel a faru. Oba objekty byly opraveny.
Spolubudovatelem nového a většího chrámu v roce 1744 byl patronátní feudál F. A. Rottal. Tento rod pocházel ze Štýrska, kde je zemským světcem opat sv.Jiljí. V minulém století dostal kostel jehlancovitou věž vysokou 56 metrů (alpská architektura) a dnešní podobu. Postavil jej stavitel a sochař Tomáš Šturm z Holešova. Roku 1791 byly na věži první hodiny. V roce 1883 požár znovu zachvátil kostel i faru. Za Oliviera Loudona byl kostel dostaven a od té doby se nezměnil. V kryptě kostela byl pochován Přemek z Víckova (zemřel 1581) jako jediný z vladařů na zdejším zámku.
Na hlavním oltáři je umístěn bývalý Hostýnský obraz Panny Marie zvaný Rottalovský, po stranách jsou sochy Františka Paluánského a Antonína Poustevníka. Kostel je chráněnou památkou, kterou spravuje Římskokatolická církev.
Roku 1744 zde nechal tehdejší majitel panství, František Antonín hrabě z Rottalu postavit kostel zasvěcený sv. Jíljí, k němuž původně přiléhala kaple sv. Kříže. Ta však roku 1789 vyhořela a již nebyla obnovena. V kostele se nachází stříbrný obraz Panny Marie Svatohostýnské, který kolem roku 1630 darovala Marie ze Šternberka, provdaná z Rottalu chrámu na sv. Hostýně. Později byl obraz přenesen do Bystřice.
