The mound on which the church stands commands views over its wide spur of land between the discharge of the Colne and the Thames. This suggests that the first church was built on the site of an older, pre-Christian place of worship. Celtic remains have been found at Church Island south of the church, which before the navigability of the Thames was accessible in times of low flow by a ford. There is a misconception that the first church on this site was built in AD 685. The earliest written evidence of a church building is dated 1179, but it may have existed by 1100. The oldest surviving part of the church is the tower, on which a plaque says it was designed by Inigo Jones and built in 1631. A large part of the body of the church collapsed in the 1820s, so a new chancel was begun after a private Act of Parliament was passed allowing what remained of the old church to be blown up. In 1827 the last remnants of the earlier St Mary's were destroyed. The present ed nave was designed by John Burges Watson and building began the following year. In 1885 a semicircular apse with three windows was added to the chancel and the organ was moved to its current position. After the Second World Warthe stone pinnacles of the tower were removed as unsafe, possibly due to a bomb landing in Wraysbury Road during the war.
The rectory, consisting after 1217–18 solely of tithes, was appropriated in 1222 to the guest-house and infirmary of Westminster Abbey. In 1225 and until after 1291 it belonged to its "hosteler" alone. Its value, including its chapels of Ashford and Laleham, was £46 13s. 4d. in 1291 per annum. After the Dissolution of the Monasteries in the 16th century the rectory passed into lay hands, and from 1725 to 1844 belonged to the Coussmaker family of Westwood, Surrey. In 1842, when Staines parishioners commuted the tithes, the great tithes of Staines alone were worth £365 which was compensated to the Coussmakers. As in most vicarages, widely the chancel repair liability on the parish's landowners has been since, technically, apportioned.
The Brindley & Foster organ, thought to date from the early 1870s, was dismantled for restoration in 1973. After examining the mechanical action, the restorers, Bishop and Sons, determined that the organ was built before 1830. However, an account in a church magazine from the 1870s indicates that the organ was installed in the church in 1871. It is thus probable that Brindley & Foster took the instrument over from its original builder, enlarged and renovated it. The organ was removed in 1885 from its original location in the gallery at the back of the nave and re-installed on the ground behind the choir stalls.
Bells
St Mary's has a ring of eight bells, all cast by the Whitechapel Bell Foundry. Richard Phelps cast six of the bells in 1734. In 1829 Thomas II Mears cast the treble and second bells and recast the tenor. The five surviving Phelps bells are listed for preservation by the Council for the Care of Churches. A 1999 survey revealed cracks in three of the bells, so in 2002 Whites of Appleton removed them from the tower, repaired the cracked bells and then sent them all to the Whitechapel Bell Foundry for re-tuning. Thereafter the bells were rehung with new wheels, headstocks and other fittings, and reconsecrated by Bishop Edward Holland at a service that same year.
Tombs
Notable people buried at St Mary's include:
Augusta Maria Byng, governess to the future Kaiser Wilhelm II and the other children of the Crown Prince and Crown Princess of Prussia.
