Vesterø Søndre Kirke, eller Vesterø Kirke, som er dens oprindelige navn, er bygget i romansk stil i ca 1250. Den er bygget af munkesten, men sydsiden er senere skalmuret med små sten (1777) og rødkalket som en af de få rødkalkede kirker i Danmark. Den ældste del af kirken er kirkeskibet. Skibets tag er forlænget hen over koret, hvor det afsluttes med en helhvalm med middelalderlige munketagsten, som efter restaurering 1994-96 er udskiftet med nye munketagsten.

Ved østgavlen af koret har der tidligere været et vindue. Dette vindue er efter restaureringen i 1995 markeret som en blænding i muren. Tårnet, hvis gavle imod sædvane er nord-sydvendte, er bygget ca. 1550. Årstallene på tårnet 1767, 1794, 1947 og 1996 angiver senere restaureringer. Gavlene på tårnet er kamtakkede og er endvidere forsynet med hvidkalkede blændinger på den nordre gavl.

Kirkeklokken er af malm og er støbt i 1640 af den franske klokkestøber Franciscus Vaillardi. På klokken er der en bibelsk indskrift på latin: "Si Deus pro nobis - quis contra nos" hvilket betyder: "Hvis Gud er for os -hvem kan da være imod os?" (Rom. 8,31). Der har muligvis tidligere været våbenhus på kirkens sydside, sværdsiden, mændenes indgang. Kun en blænding i muren viser, hvor døren fra våbenhuset til kirken kan have været. Det nuværende våbenhus på nordsiden, spindesiden, kvindernes indgang, er bygget i 1885, da det afløste et tidligere våbenhus af bindingsværk. I kirkemuren - både udenfor og inde i kirken samt i våbenhuset - er indmuret ligsten. De har tidligere for det meste ligget i kirkegulvet, men blev taget op ved kirkens restaurering i 1947. Nogle af ligstenene har dog været på kirkegården. Selve kirkeskibet har bjælkeloft, mens der i koret og i underrummet under tårnet er sengotiske hvælvinger, henholdsvis kryds- og stjernehvælv. Korbuen er romansk og tårnbuen er i gotisk stil.