The church is largely 19thc. and comprises a W tower, a nave with N and S aisles, a chancel flanked by a vestry (N) and chapel (S). When the church was substantially rebuilt in 1878, the nave arcades were retained.

King Offa is said to have granted land in Bexhill to the Bishop of Selsey in 772, allegedly for the building of a minster. The holding had expanded by 1066. The manor was seized c.1077 as part of the Rape of Hastings, by Count Robert of Eu who granted the church to the college of St-Mary-in-Castro, Hastings, in aid of the prebends. Two churches, probably Bexhill and Northeye, are mentioned in the Domesday Survey. In 1148 Count John restored the vill and churches to Bishop Hilary of Chichester, as confirmed by King Stephen. The surviving 12thc. nave arcades were erected after the church had been returned to Chichester.

The original nave arcades pierced an earlier wall containing herringbone masonry. There are slight differences between the N and S arcades: the S capitals are shorter than those on the N due to the presence of an additional moulding at the base of the abacus; the S capitals are carved with stylised foliage, while the N capitals, including the fluted pier capital, are variations on the scalloped form; the lower tori of the S bases are fatter than those on the N, and the neckings on the S have rounded profiles while those on the N are roughly chamfered. Despite these differences the arcades belong to the same campaign and it is difficult to deduce which was erected first. The range of capitals can be compared with Icklesham nave, where one also finds multi-scallop capitals, fluted leaves separated by projecting triangles, and rows of pointed and spade-shaped leaves. The two monuments certainly emerged from the same artistic milieu and must be approximately contemporary, c.1160-75. The nave arcades of Battle, St Mary and Herstmonceux, All Saints, although `post-Romanesque', may be later works by the same group of masons.