The aisleless nave of Old Shoreham is Anglo-Saxon. The tower which once stood at its W end was probably adapted as a nave extension in the mid-12thc., when the central tower and transepts were erected. The large chancel dates from the 14thc., and includes a tie beam carved with dogtooth. In 1840-44 two vestries were built in the angle of the N transept and chancel, and the church was restored.

The church of Old Shoreham is recorded in Domesday Book. In 1073 William de Braose granted the tithes to St Nicholas, Bramber, but c.1080 he granted Shoreham church to St Florent, Saumur, with its dependency Sele Priory holding the advowson. The church was restored 1840-44 by J. M. Neale and J. C. Buckler (Cambridge Camden Society), who built two N vestries (a choir vestry and a vicar's vestry) on the site of the 14thc. N chapel. The chapel arch was restored after long exposure to weather. The N transept, and most of the church windows, were restored at the same time.

The dedication to St Nicholas is recorded in the Sele Chartulary, 47, c.1080.

The nave tie-beam appears to be of 12thc. date, in which case it would represent the sole piece of surviving 12thc. wood-carving in Sussex. However, the VCH expresses the opinion that it is of the 16thc. or early 17thc. (VCH, vi, p.170).