St Augustine, who in 7th century, brought Christianity to the south eastern corner of England. He became the first Archbishoterbury. With him were Justus and Paulinus, and it was Justus who founded the diocese of Rochester and became the first Bishop of Rochester in 604 AD. Paulinus was sent north. Paulinus returned from Northumbria in 633AD and became the third Bishop of Rochester, continuing his missionary work in Kent. It is thought he probably sailed down the River Medway from Rochester, past the Saxon Cathedral Church, up into the River Thames and on into the River Cray, which was then a navigable waterway for small vessels. He continued up the River Cray, where the dedications of the Churches of St Paulinus, Crayford and St Paulinus, St Paul’s Cray (now closed) commemorate the route of his journey. St Paulinus also brought the message of Christianity to the settlements surrounded by woods along the River Cray, including a hamlet known as Fot’s Cray, named after Godwin Fot, a local chieftain.
At the time of St Paulinus’ visit, a wooden Saxon Church was probably erected on the site of the present Church of All Saints: the original size of Foots Cray Church exactly matched the dimensions of a Saxon Church. The present Church, perpendicular in style, dates from about 1330. The Lord of the Manor at that time was Sir Simon de Vaughan, who was buried with his wife about 1350 in an altar tomb. The remains of their effigy, originally under the arch which divides the Lady Chapel from the nave of the Church, are now under a low Tudor brick arch in the Chapel. The font is Norman, dating from the late 12th century. The Church was extensively altered in 1861. Old box pews with doors were removed, as were two galleries in the Church. The nave was extended westwards with the bell tower at the west end of the Church left standing on four oak posts, so that the bells are now rung from the centre of the aisle. The west door case and porch, dating from about 1500, and the door to the Church, dating from the time of Oliver Cromwell were reset at the end of the longer nave.
In 1872 the Church was lengthened eastwards into the chancel and the reredos was added. The present organ was presented by Sir John Pender, the founder of Cable and Wireless, who is buried in the Churchyard, where there is an imposing memorial to him. A remaining panel from the rood screen which would originally have separated the chancel from the nave has been incorporated into the front of the prayer desk and a part of the rood loft stair remains in the small turret which now leads to the pulpit through a depressed Tudor arch. The arch has a Jacobean gate dated 1638 and was probably a gate from the original communion rails put to a different use. The alabaster pulpit was erected in 1886 and was presented by the Harenc family of Foots Cray Place. The majority of the stained glass windows are Victorian, although the one in the west wall of the Lady Chapel is much older and the two windows on the south side of the nave at the east end are 14th century work. Altar pieces of the Ten Commandments and the Lord’s Prayer with pictures of Moses and Aaron, painted in 1709, are now on the walls of the nave. The Church spire, re-shingled in 2004, was built by Lord Waring to commemorate the coronation of King Edward VII. The carved choir stalls and chancel screen also date from this time. In the Churchyard is an iron grave slab commemorating ‘Martin Manning, Yeoman’ dating from 1656. Also to be noted is the mass dial on the south side of the outside of the wall.