Vester Vedsted Kirke staat witgekalkt en met lood gedekt op een lage heuvelrug dicht bij de Waddenzee. Het is niet alleen de ligging die haar de moeite waard maakt: aan de noordzijde van het schip zijn nog delen van het oorspronkelijke romaanse metselwerk te zien, waar de tufstenen als een tastbaar spoor van de oudste bouwfase van de kerk liggen.
De oude noordmuur is de beste plek om de middeleeuwse kerk van buitenaf af te lezen. Hier zijn de muurvlakken verdeeld door lisenen en afgesloten met trapfriezen onder zaagtandversiering. De toren vertelt een ander verhaal. Hij heeft een Tørninglen-dakvorm met vier spitse gevels en een spits, en vooral aan de zuid- en westzijde zitten veel muurankers als zichtbare tekenen dat de toren steun nodig heeft gehad.
Als de kerkruimte open is, zijn er meerdere details te vinden zonder dat je vooraf de hele kunstgeschiedenis hoeft te kennen. De triomfboog tussen koor en schip is bewaard gebleven, het koor heeft gewelven, terwijl het schip een vlak plafond met beschilderde balken heeft. Het altaarstuk bevat ouder houtsnijwerk, en aan de noordmuur hangt Anna te Drieën, de figuur die achterbleef toen andere altaarfiguren later uit de kerk verdwenen. Het kerkschip draagt de naam Havfruen.
