Kostel má svůj původ v době založení horního hradu a je znám farářem Janem r. 1330. Kolem r. 1600 kostel přestavěl Jan Žalkovský, o čemž svědčí trojúhelníkový kamenný klenák z nadvchodu s vytesanými počátečními písmeny jeho jména -JZZZ (J. Ž. z Žalkovic) a s jeho znakem. Byl luterán, stejně jako otec Matyáš a měli utrakvistického kněze. V kostele v gotických skružích byly zazděny erby - sovinecký ze 14. století - Elišky z Kumburku a Machny z Valdštejna z 15. století. Když Žalkovský stavěl kostel, postavil věž 9 sáhů od dnešní sakristie jihovýchodním směrem, aby jej zabezpečil proti blesku a možnému požáru. Na věži byly zvony, pod ní kostnice, a na zdech se zvěčnil čtyřmi reliéfy (dva jsou s jeho jménem a další patří jeho dvěma manželkám). Po výstavbě nových věží r. 1847 (v rámci dnešního kostela) byla stará věž zbořena a reliéfy byly zazděny do hřbitovní zdi, podélné s kostelem. Erby - reliéfy byly později vsazeny do venkovní zdi kostela a nyní (po dobu opravy fasády) jsou uloženy v chodbě sakristie kostela.
Dnešní kostel byl stavěn ve slohu tudorovské pseudogotiky - loď chrámová r. 1847 a kněžiště s oltářem až v r. 1890. Při každé stavbě byla zrušena v kostele jedna hrobka. Původní starý hřbitov býval okolo kostela. Ke kostelu patřívalo sedm obcí: Otaslavice Horní a Dolní, Brodek, Sněhotice, Kobylničky, Myslejovice a Dobrochov, což dokládají zápisy ve staré farní matrice, vedené od r. 1684.