On the west side of Mark Lane, where the Tower and churchyard still stand, entrance by a passage out of Fenchurch Street (O.S.). In Langbourne Ward. The parish extends into Tower and Aldgate Wards.
Earliest mention found in records : A deed of 1177 relating to land of Blanchesapeltuna is endorsed " Staniggecherch " (Anc. Deeds, A. 7295).
Names and forms of names : " Parish of Stanenechirche," c. 1170-87 (Anc. Deeds, A. 2406). "Ecelesiam de Staningehage," 1 Rich. I. (Cott. MS. Faust. B. II.). "Onmium Sanctorum de Stanene Chch. c. 1218 (Ducarel, St. Katherine's, p.108). "All Hallows de Staningecherch," 1280-1 (Ct. H.W. I. 51). " All Hallows de Stanyng," 1372 (ib. II. 146).
" Commonly called Stane Church as may be supposed for a difference from other " Churches of that name in this Citie, which of olde time were builded of timber, and " since were builded of stone " (S. 205).
Loftie suggests that the name may be derived from a certain holding in the City mentioned in Domesday Book, and in a charter of Edward the Confessor, as belonging to the manor of Staines (London, p. 164), and Kingsford that it was known as the " parochia de Stanenetha " (stone hithe), 1194 (Cart. de Colchester, 298) (ed. Stow, II. 308). But this is not a general form of the name.
Povah suggests 1140 as the date of the erection of the stone church, rendered desirable by the Fires of 1087 and 1136 (Annals, 317). Repaired 1630. Escaped the Fire 1666, but afterwards fell down 1671 and rebuilt about 1683. (Strype, ed. 1720, I. ii. 158-9). Again fell down 1761 (Welch).
Church, except the tower, taken down 1870 and the parish united to St. Olave Hart Street. The tower is still standing and is in the Perpendicular style, over 400 years old. It was purchased, together with the site of the church, by the Company of Clothworkers from the Ecclesiastical Commissioners on the understanding that they would keep the tower in repair and would not build on the site, except on defined portions fronting Mark Lane (Povah, Annals of St. Olave, Hart Street, and All Hallows Staining, 317, 324).
A Rectory. Patrons : in 31 Ed. I., in private hands, J. de la Barre (Lib. Cust. I. 238). Afterwards belonged to the de Walthams and eventually was given by the Bishop of London to the Abbot and Convent of St. Mary Graces (Newcourt, I. 255-6). After the Dissolution, it remained in the hands of the Crown.
It is open to question whether the church and parish of " All Hallows Colemancherche " and " Colemancherche," which are treated as separate churches in the Nomina Beneficiorum (Lib. Cust. I. 230 et seq.), coalesced subsequently with the church of All Hallows Staining, or whether, as seems more probable, All Hallows Colemancherche is identical with St. Katherine Colman (q.v.).