The W tower and a corner of the nave are all that survive of an aisleless church of c.1100. The neo-Norman doorway in the W wall of the tower replaced a simple doorway, itself an insertion. Elements of the church dating from the 12thc. are a fragment of the N aisle, c.1100-20, and the Chapel of St John, c.1190, which has an entrance arch with chevron but is otherwise stylistically `Transitional'.

Guestling, but no church, is mentioned in the Domesday Survey. It is recorded, however, that in the time of Count Robert of Eu (1070-1090), Geoffrey, brother of Canon Hugh of St-Mary-in-the-Castle, Hastings, gave Guestling church to the prebend founded by Walter fitz Lambert of Scotney, under whom the manor of Guestling was held. The W tower, which was added to an existing nave, was probably erected soon after that event, c.1090-1100, and the N aisle followed shortly after. It has been suggested that the Chapel of St John was erected by John of Guestling, a Justiciar, c.1200. The church suffered from a restoration of 1886 and a fire on 25 March 1890.

The capitals of the W tower bell-openings, although weathered, may date from the 19thc. restoration and cannot be entirely trusted. The single order bell-openings resemble others in the area, e.g. Burwash and Wadhurst, whose capitals have either been renewed or are very weathered. Guestling capital III.2.i, however, finds close parallels on the altogether more ornate bell-openings of Icklesham, which is the next village. Whether the same early 12thc. workshop was involved, or whether the restorer of Guestling was inspired by Icklesham is, as yet, unclear. The E arch of the N aisle is particularly elaborate as it is the entrance to the Chapel of St John the Evangelist. It juxtaposes Early English features, such as keel mouldings and stiff-leaf capitals, with chevron, and probably dates from the very end of the 12thc. It is closely related to the nave arcades of Eastbourne, St Mary (not included).