The church is of local brown sandstone. The W tower is medieval, but the rest is Victorian (1856) with some medieval fixtures and fittings. These include a blocked Norman window with an arched lintel at the E end of the N aisle, and a Norman pillar piscina.

East Hoathly is not mentioned in the Domesday Survey. The pillar piscina, evidence of a Norman church on the site, was published by Mark Antony Lower in SAC 1856. It had been discovered 'in the thickness of the foundation wall' of the chancel, in October 1855, by workmen engaged in demolishing and rebuilding the E end of the church. The three pieces - capital, shaft and base - were found separately but 'uninjured', were reassembled and installed in the new chancel. Discovered at the same time was 'the stonework of three diminutive Norman windows'.