The first firm evidence of a church in Grays comes in 1040 AD when a priest, Wulfstan the Wild One, inherited the Manor of Thurrock although there is no structural evidence of a Saxon church. The earliest architectural style identified in the present structure and in old drawings is Norman, and it has been concluded that the oldest part of the present building dates from a few years either side of 1100 and consists of the present chancel and part of the nave built by the Peverels, who were then Lords of the Manor.

Sometime between 1152 and 1159 the church was given to the Knights Hospitallers of St John of Jerusalem by William de Ferrers. He had come into possession of the Church and Manor by marrying Margaret the daughter of William Peverel and grand-daughter of the first Norman Lord of the Manor. William de Ferrers not only gave away the Church "for the safety of my soul, and for that of my wife, and for those of my predecessors and heirs" but also sold the Manor at about the same time to Isaac, son of Josce the Rabbi, showing concern for both his spiritual and earthly needs. The manor came into the hands of the King probably on Isaac’s death as a method of collecting death duties from those who were not the King’s subjects. Their lands were confiscated and then sold back to the heir at a substantial discount. It was Isaac's son who sold the Thurrock manor to Henry de Grey in 1194. So started the long association of the de Grey family with the area, which was to give its name to Grays Thurrock. (to learn more about Henry de Grey click here)

Returning to the church, the south chapel (now the organ chamber) is entered through an arch which is dated to 1280-90 and some authorities date the chapel's construction to that time. However at least two 19th century drawings show early Norman round-headed windows in its east and west walls and it is more likely that the arch was introduced in order to improve access to the chapel and that the chapel dates from the original construction of the church, or even before, for it was a manorial chapel. The tower was added at about 1230.

In the early 19th century the population of the small market town of Grays was growing with the industrial development and the church had to provide more accommodation. In 1846 the church was largely re-built and galleries added in the base of the tower and at the west end. This was not big enough by 1867 and the nave was extended again to its present length and the north aisle added.

An internal re-ordering took place in 1935 when the pipe organ was moved into the south chapel and the ground floor of the tower converted for use as the Lady Chapel.

In 2008 a major re-ordering was carried out. Internally the floor of the nave and north aisle was raised and carpeted and under-floor heating introduced. All the Victorian pews were replaced with chairs and a glazed general purpose area with adjacent toilets provided at the west end of the north aisle. The clergy stalls were moved to the east end of the choir to provide space for a dais with a nave communion table. The lighting and sound system were replaced. Externally the major change was the closure of the south porch (to be used as a store) and the making of a new south doorway at the west end of the church. The church is a Grade II listed building.