According to the Gutasaga, a man called Lickajr the Wise built one of the first churches on Gotland in Stenkyrka. If true, this first church was almost certainly wooden. The name Stenkyrka (literally in Swedish: stone church) implies that also the stone church is very early, from a time when buildings made of stone (rather than wood) was still a phenomenon unusual enough to give name to a place. This first, Romanesque church is also gone, but traces have been found and archaeologists have been able to determine that it was a small church with tower, nave and choir.
The Romanesque church was successively replaced by the presently visible church starting in the mid-13th century. The choir was rebuilt first, followed by the nave, which was inaugurated by the bishop of Linköping in 1255. The tower was added during the 14th century, and modelled after three similar city churches (since destroyed) in Visby.
The church underwent a restoration in 1954-55.
The church is dominated externally by the accomplished tower, one of the finest church towers on Gotland. The church has two simple Romanesque portals and a Gothic tower portal. Internally, the church is richly decorated with frescos, dating from three different periods. The oldest ones are from the middle of the 13th century and mainly ornamental. Later but from the same century are a number of paintings depicting imaginary animals, drapery and marble imitation. The youngest frescos, from the end of the 14th century, depict figures and scenes from the bible.
The furnishings are mostly from after the reformation. A finely carved crucifix dates from the late 14th century, and the baptismal font is from the 12th century. The church is also the location of the oldest dated gravestone on Gotland, from the year 1200.