Den hvidkalkede kirke er bygget af tegl og fundamentet er af granit. Den ældste del skibet er bygget i tiden mellem 1175-1200 og koret i 1250. Tårnet blev bygget i forbindelse med en større ombygning i 1500-tallet. Spiret med de fire spidsgavle blev genopført efter et lynnedslag i 1845.
Vester Vedsted Kirke kan føres tilbage til ca. 1175, hvor den grundlægges på klitten i Vester Vedsted. Oprindelig er der tale om en tufstenskirke. På kirkens nordside er tufstensmuren bevaret fra sokkel til vinduer.
I den katolske tid var kirken viet til Skt. Andreas. Der er ingen oprindelige kalkmalerier, men i koret er der kalkmalerier fra 1916.
Altertavlen og billedet af den sidste nadver er fra begyndelsen af det 18. århundrede. For oven prydes tavlen af to renæssancefigurer af Peter og Paulus. Figurerne i nicherne på hver side af alterbilledet forestiller Faderen med verdenskuglen i sin hånd og Kristus som den gode hyrde. Tavlens bund prydes af syv små reliefbilleder af gammeltestamentlige profeter og konger.
Prædikestolen er fra 1625 og fremstår med reliefferne: Bebudelsen, hyrdernes tilbedelse, omskærelsen og Jesu dåb i Jordan.
.svg)
