Fleet Grade I listed Anglican church, dating from the late 12th century, is dedicated to St Mary Magdalene. The church tower with spire is detached from the nave by . The fabric is mainly Decorated in style, with Early English arcades and a Perpendicular west window. According to Cox (1916), the church was restored in 1860, when the chancel was rebuilt, although the canopied sedilia was retained. In 1964 Pevsner noted 1798 repairs and considered the church "over-restored". He dated a chancel rebuild to 1843, questioned if it was "done correctly", and recorded Victorian tracery in the aisle windows, a blocked doorway to a previous chapel in the chancel, "fine busts of great variety", a Decorated-style sedilia and piscina with ogee arches and crocketed gables, a reredos dated 1790, and a defaced 14th-century effigy.
Pevsner also recorded an 1854 red-brick rectory designed by Benjamin Ferrey, and a motte south-west of the village where 11th- and 12th-century pottery has been found. The English Heritage record for the now ploughed-down motte site details finds from the Iron Age to the 18th century.