Gotický kostel vznikl pravděpodobně v poslední čtvrtině 13. století zásluhou zakladatele hradu Fulštejna Herborda z Fulštejna a jeho synů Jana a Ekerika. Byl postaven na místě staršího pohřebiště, které sloužilo už od poloviny 13. století. Není zřejmé zda měl nově vznikající kostel na tomto místě nějakého (pravděpodobně dřevěného) předchůdce. Kostel svatého Martina byl postaven jako rozměrná jednolodní stavba, jejíž loď byla na nárožích podepřena diagonálně orientovanými opěráky. Stejně i velký obdélný presbytář byl na nárožích a v ose jižní zdi opatřen opěráky. Ze severu přiléhala k presbytáři přízemní sakristie. V době svého vzniku patřil mezi venkovskými kostely na Moravě a v Čechách k velkým stavbám. Kostel tak měl už svou velikostí demonstrovat společenské postavení rodu Fulštejnů v celé oblasti. Někdy kolem roku 1285 byl kostel vysvěcen.

Pravděpodobně během česko-uherských válek v 15. století kostel vyhořel. Snad v roce 1486 zahájil tehdejší vlastník Bohušova Jiří Sup z Fulštejna rekonstrukci kostela.

V letech 1727–1728 byl kostel zednickým mistrem Johannem Kunigem z Osoblahy barokně přestavěn. Většina starých gotických oken byla tehdy nahrazena novými barokními. Výrazným způsobem do historie kostela zasáhl tragický požár 24. prosince 1800, při kterém v kostele uhořelo pět lidí. Z kostela se po požáru dochovaly jen obvodové zdi.

Na začátku 20. století (1907) byla zbořena stará gotická sakristie a byla nahrazena novoklasicistní přístavbou.

Po povodních v roce 1997 pravděpodobně vlivem změny hydrogeologických vlastností podloží v okolí výrazně stoupla vlhkost v kostele. Při úpravách fasády došlo k objevu zachovaného kamenného gotického portálu na jižní straně presbytáře a také profilovaného ostění původního (později zazděného) východního okna v presbytáři. Souběžně s opravami probíhal v kostele v letech 1999–2000 archeologický průzkum, při němž byly pod podlahou presbytáře nalezeny kamenné náhrobky biskupa Jindřicha z Fulštejna, Ekrika Supa z Fulštejna a Václava Sedlnického z Choltic.