The church was built of local limestone, with a straight-ended chancel and sacristy to the north, a taller and wider nave, and a west tower matching the nave in width. The chancel and nave were built together around the mid-1200s, with the tower following towards the end of that century; the sacristy was added later, though sources differ on the date, with one suggesting shortly before 1650 and another placing it in the seventeenth century more generally.
Three original doorways survive, each with simple Gothic mouldings; the western portal, the largest, is decorated with foliage ornament and was probably the main entrance. The narrow pointed window openings to the east and south are original, as are the tower's paired colonnette sound-openings.
Inside, the church is fully vaulted. The nave's four masonry vaults are carried on a single sturdy central pillar, an unusual and striking feature, while the chancel and ringing chamber each have a single vault of their own. Fragments of medieval wall painting survive from the 1400s, along with an unusual ornamental decoration from the later 1500s.
A major fire in 1676 is said to have led to rebuilding work, and as a result the church lacks medieval fittings. The font, dating from the 1630s, originally stood in Visborg castle church and was moved to Fleringe after the fire. The altarpiece, made by Rasmus Bartsch, is dated 1701, and the pulpit was added in 1726.
Outside, an open area to the west of the church still has its church stables, unusual for Gotland, and a medieval barrel-vaulted lychgate stands in the churchyard's south-west corner, with traces of a second gateway visible in the north churchyard wall.