This church comprises a W tower, a 12thc. aisled nave and a 19thc. chancel. The demolition of the medieval choir, transepts and central tower, dilapidated since the Dissolution, was begun in 1577 and completed in the 17thc. A new chancel and W tower, which occupies the site of the W bay(s) of the nave, were then constructed. What was lost at the E end must have been largely of early 12thc. date, judging from the surviving W piers and arch of the crossing and the E arches of the S and N aisles which formerly opened into the transepts. The nave was erected later in the 12thc. The present chancel is of the 19thc.

Steyning church, said to have been founded by St Cuthman in the late 8thc. or early 9thc., was under royal patronage by the mid-9thc. when Ethelwulf (d.858) was buried there. Edward the Confessor gave the church and manor to the Abbey of Fécampc.1047, but it is uncertain if Fécamp took possession before Harold revoked his predecessor's gift. William pledged to uphold Fécamp's claim if his invasion proved successful, and indeed, in 1086, he confirmed its rights. Two churches are mentioned in the Domesday Survey. Steyning church would have held considerable political significance in the late 11thc. It may have been collegiate in 1086, as it certainly was by 1185, when a provost and three secular canons, each with a prebend, are recorded.

the 1263 dedication to St Andrew is recorded in Cal. Papal Reg. i. 387.

The earliest element of the church seems to be the E arch of the S aisle. One capital is carved with affronted lions, a subject which had been employed earlier at Caen and Durham, and was to become one of the most popular motifs of 12thc. sculpture. It is flanked by two foliage capital, one based on the Corinthian order, the other based on `Winchester Acanthus'. In neither case is the foliage fleshy, it is depicted by crotchets or curls, sometimes sprouting from one another. This feature derives from the Scandinavian Ringerike style, which can also be seen in nearby Sompting church. The Ringerike style recurs on the relief carved into the S respond shaft, showing men clambering amid foliage tendrils. The design of this panel finds extremely close parallels in manuscripts and ivories ofc.1100 (eg Arundel 60 f.13,c.1080; an ivory in the VandA,c.1100 illustrated by Swarzenski, pl.204).

Johnston dated this early work at Steyning toc.1100 (1914) and laterc.1120 (VCH, 367); Zarnecki (thesis) dated itc.1140. Zarnecki (PhD thesis) compared the Steyning capitals with examples in the Canterbury crypt, which he suggested as a source, although he also noted the parallels between Sompting and Steyning.

The only other part of the building which could feasibly date from c.1100 is the exterior of the N clerestorey, which has a rubble facing. The windows have plain, continuous arches.

The W crossing arch, the E arch of the N aisle and the E responds of the nave arcades belong to the same campaign, and cannot be earlier than the second quarter of the 12thc. The chevron and capitals of these bays find close parallels at Amberley church (compare Amberley chancel arch, inner and outer archivolts W side, with Steyning, E arch of N aisle, inner archivolt N side; Amberley chancel arch, inner order, S capital, with Steyning, N nave arcade, bay 1, outer order N side, E capital; Amberley chancel arch, outer order W side, N capital, with Steyning, E arch of N aisle, inner order, S capital). Reset chevron voussoirs in the W tower have flat bands instead of rolls, another feature paralleled at Amberley.

The form of the Steyning nave arcade was popular in Sussex, but nowhere else is it treated so elaborately. Fundamental design differences in the clerestorey windows point to a complex architectural development at that level in the building. There are also differences of detail between the main N and S arcades of the nave. Certain motifs (soffit rolls or coussinets, fluted palmettes, beaded cable roll, triangular fluting, etc) of the S arcade recur in the S doorway and chancel arch of Winchfield church in Hampshire, which was surely executed by the same workshop.

The font can be compared with that of New Shoreham. Despite Drummond Roberts's description of it as Sussex marble, recent scholarship has confirmed that the bowl and its Victorian support are of Purbeck; recognisable by the smaller fossil shells.