This unusually large parish church comprises an aisled choir, crossing tower, transept, and one nave bay, the remainder of the nave having collapsed in the early 18thc. The church was founded in the late 1120s or 1130s (see History, below), and the crossing tower (except for the upper bell-stage), transepts and nave date from the mid-12thc., as does the font. The first chancel had an apsidal termination, and a campaign to add aisles to its sides was undertaken - but possibly not completed - around 1160. The chancel was rebuilt as a fully-fledged choir, complete with aisles and galleries, in the late 12thc. and early 13thc. At the same time an additional bell-stage was added to the tower. The footings of the nave walls, which had collapsed by 1720, can be seen in the graveyard to the W of the church.

St Mary de Haura is first recorded between 1093 and 1139, when Philip de Braose (or Briouze), son of William de Braose, granted it to St Florent, near Saumur, on the Loire (Woodcock 1992, 91-92). Although this grant is traditionally thought to have been made between 1096 and 1103, a notification of 1144 indicates that it can be dated to the episcopacy of Seffrid I, who became Bishop of Chichester in 1125. A foundation date of c.1125-39 would agree with the style of the earliest surviving parts of the building, which appear to have been erected in the 1140s.

Mid-12thc. documents refer to the church as a chapel, which received all tithes pertaining to the port and all rents in tithe and so it must have accrued considerable wealth. By the 1170s, however, St Mary de Haura had become a parish church in its own right. It was in the late 12thc., when the port of New Shoreham was at its peak, that the rebuilding of the chancel was undertaken, and although this work has been associated with the baronage of William de Braose III, who fell from royal favour in 1212, there is no evidence of his direct involvement. The church was appropriated to the priory of St Peter at Sele, a cell of St Florent, in 1396. From 1459 until 1948 it was held by Magdalene College, Oxford, and in 1948 it was transferred to the See of Chichester.

The nave fell into disrepair in the 17thc., and by 1720 its eastern bay, deprived of its aisles, had been converted into a W porch (B.L. Add. MS. 5673, f.43). Otherwise, only a section of the W wall remained above ground.

The church was thoroughly restored in 1876 by Arthur Loader; it is worth noting that some of the stonework replaced at that time is now in a very poor condition. In 1915 the choir was excavated by Walter Marshall, revealing that the original chancel was narrower than the present structure, and had an apsidal termination. Scarring on the E faces of the transepts led Marshall to postulate apsidal chapels in these positions, but when the areas to the E of the transepts were excavated in 1949, only straight walls were uncovered. Rather than representing apsidal chapels, these were probably the remnants of aisles which would have been added to the original chancel, work which would have involved the demolition of any transept chapels standing prior to that time (Woodcock 1992, 93-94).

The Sele Cartulary, nd, refers to the dedication to St Mary De Haura.

The design of the crossing, transept and nave suggests that the church of New Shoreham was begun closer to 1139 than to 1103, as previously believed. The sculpture of the crossing is mature 'High' Romanesque, and would support a date in the 1140s. If the church was built in the traditional manner, from E to W, the first chancel would have dated from the 1130s. The design of the nave has been placed in the 1160s, leading Woodcock to suggest that it replaced an earlier structure (Woodcock 1992, 95). However, there is no reason to date the nave very much later than the crossing and transepts: the multi-scallop capitals are simpler than those of the crossing, but incorporate beaded astragals; the labels of the arches are decorated with sawtooth, and the imposts have a simple hollow chamfer. Moreover, the clerestorey windows are very similar to those of the transepts, which Woodcock thinks were raised in the 1160s. The present W doorway, probably the original W doorway, is ornamented with beakhead and scallop capitals, and cannot be dated much later than the mid-1150s. It seems likely that the entire church could have been erected in a straightforward campaign from E to W betweenc.1130 and c.1160.

At some time in the second half of the 12thc., aisles were added to the existing chancel. These may never have been completed and, for whatever reason, the entire E end was demolished and rebuilt around 1200. The design of the choir is far from homogeneous: most strikingly, the N arcade has alternating cylindrical and octagonal piers, while the S arcade has compound piers of unusual undulating profile throughout. With the exception of the Late Romanesque blind arcading in the aisles, the detail of the choir is uniformly Early English in conception, consistently displaying features such as keel mouldings, mature stiff-leaf foliage, a quatrefoil frieze, and shallow attic bases with leaf spurs. A highly plausible explanation for the stylistic discrepancy between the Romanesque blind arcading and the Early English style of the remainder of the choir has been put forward by Woodcock. She has suggested that most of the elements composing these blind arcades were retrieved from the earlier campaign, now datable to c.1160, to add aisles to the original chancel (Woodcock, 99). A close study of the blind arcade reveals a misalignment of blocks, especially amongst the chevron mouldings, which proves that the material was, indeed, reused. It was padded out with elements dating from c.1200, notably the arches of the W bay on the S side, which are carved with deeply undercut foliage related to that of the N arcade, rather than with chevron, and many of the capitals, especially on the S side.

The New Shoreham choir is often dated to c.1180, but probably began in the 1190s or c.1200. Locally, it is related to the post-fire (ie: post 1187) rebuilding at Chichester Cathedral, and possibly to the choir of Boxgrove Priory. It has also been compared with St Mary's, Reigate (Woodcock 1992, 100).

Several worked stones attributed to St Mary de Haura are displayed in Marlipins Museum, Shoreham-by Sea.