Ei ole täyttä varmuutta siitä, mikä on Viron vanhin kirkko. Todennäköisesti vanhimmat pienet sakraalirakennukset olivat puisia kappeleita, jotka ovat hävinneet jälkiä jättämättä. Tutkijoiden suosituin ehdokas vanhimmaksi säilyneeksi kirkkorakennukseksi on Valjalan kirkko Saarenmaalla. Voi perustellusti väittää, että se on vanhimmilta osiltaan sekä Viron vanhin kivirakennus että vanhin (säilynyt) kirkko. Ilmeisesti heti saksalaisvalloituksen (1227) jälkeen rakennettiin lähelle tärkeää Valjalan maalinnaa kivestä pieni kappeli. Kirkoksi se laajennettiin 1240–1260-lukujen aikana, niin että alkuperäinen kappeli muodosti uuden kirkon kuoriosan.
Valjalan kirkko ryöstettiin ja tuhottiin osittain vuoden 1343 ns. Yrjönyön kapinan yhteydessä, ja niinpä vuoden 1360 paikkeilla kirkkoa korjattiin ja se sai myös uuden apsiisin. 1600-luvulla kirkko sai tornin, 1757 ulkopuolelle rakennettiin tukipilarit, tornin huippu muutettiin 1770-luvulla barokkityyliseksi ja kun kirkkoa vielä korjattiin vuonna 1926, niin Viron kauneimpiin kuuluvan kirkon tarina onkin lyhyesti kerrottu.
Mielenkiintoisia yksityiskohtia ovat erityisesti Valjalan kirkon kolme portaalia, joista tärkein on vaikuttava eteläportaali, joka ei sijaitse aivan keskellä nykyistä kirkon päätyä. Portaalin yläpuolella oleva kummallinen kaari on merkki keskenjääneistä aikeista pidentää kirkkoa etelän suuntaan. Kaikki kolme kirkon portaalia ovat vielä pyörökaarisia eli selvästi romaanisen tyylin mukaisia, mutta ikkunat ja holvit viittaavat jo selvästi gotiikkaan.
Sisällä kirkossa huomio kiinnittyy ensimmäisenä entisen kappelin, nykyisen kuoriosan seinämaalauksiin, jotka lienevät esittäneet mm. 12:ta apostolia. Maalaukset ovat valitettavasti pahoin haalenneet restaurointiyrityksistä huolimatta. Kirkon kalkkikivinen mahtava kastemalja on 1200-luvun puolivälistä ja arvellaan, että sen valmisti westfalenilainen mestari alun perin Haapsalun tuomiokirkkoa varten. Kirkossa on kaksi barokkityylistä epitafia 1600-luvulta. Puuseppä Nommen Lorenzenin valmistama alttari on 1820-luvulta, varsinainen alttaritaulu saman vuosisadan jälkipuoliskolta ja Gustav Normannin urut ovat vuodelta 1888. Dolores Hoffmannin lasimaalaukset 1970-luvulta kirkon ikkunoissa sopivat yllättävän hyvin yhteen sisätilojen paljon vanhempien taideteosten kanssa.
Kirkon vieressä on Valjalan Viron vapaussodan muistomerkki, joka pystytettiin alun perin vuonna 1923, mutta tuhottiin neuvostokaudella. Arkkitehti Andres Mändin tekemä muistomerkin kopio paljastettiin samalla paikalla vuonna 1993.