Podle pověstí byl kostel postaven v letech 1030 až 1050 z pálených cihel, které prý byly na vozech dovezené až z Říma, podle jiných verzí se jednalo aspoň o římské cihly. Pod vlivem těchto pověstí byl kostel pokládán za nejstarší cihelnou stavbu na Moravě. Stavební průzkum tyto domněnky nepotvrdil a na základě nálezů kamenických značek velehradské stavební huti byla výstavba románské části kostela datována až do 30. let 13. století. I tak je tato pozdně románská stavba nejstarší zachovanou památkou na Kyjovsku. V roce 1729 byl kostel rozšířen západním směrem, koncem 19. století byla zřízena hudební kruchta a v roce 1950 oratoř. Při té příležitosti bylo objeveno (a současně i zničeno) románské okno. V roce 1969 bylo odkryto zachované původní režně zdivo jádra stavby a ve vnějším líci otevřena románská okna a portál v jižní zdi lodi. Původní podoba kostela je známa ze staré kostelecké pečetě. U kostelní zdi volně leží dvě kamenné nádoby, prý se jedná o nádoby v nichž se brousily meče a další zbraně.