Kyrkan är enligt Gutasagan den första kyrkan i Nordertredingen uppförd av Likair den vise. Enligt sägnen lär socknen fått sitt namn efter denna tidiga och enastående kalkstensbyggnad. Kyrkan, som den ser ut idag, uppfördes i etapper under 1200-talet och i gavelmurarna återfinns rester av en romansk absidkyrka. Kor, långhus och tornet uppfördes i nämnda ordning. Tornet, med sitt galleri på tre sidor, kom till och med att överträffa Sankta Marias torn på Visby domkyrka. Kyrkan är rikligt prydd med medeltida målningar där triumfbågens kvadermålning från mitten av 1200-talet är den äldsta. I tornvalven återfinns marmorimitationer från 1200-talets senare del. Övriga målningar utfördes troligen under slutet av 1300-talet. Stora delar av de ursprungliga målningarna är tyvärr utplånade.