The earliest known mention of the cemetery comes from John Stow's A Survey of London (1598), which describes a "Single Woman's churchyard" in Southwark, near the Clink: Next on this [west bank of the Thames] was sometimes the Bordello, or Stewes, a place so called of certain stew-houses privileged there, for the repair of incontinent men to the like women ...

I have heard of ancient men, of good credit, report, that these single women were forbidden the rites of the church, so long as they continued that sinful life, and were excluded from Christian burial, if they were not reconciled before their death.

[6] The graveyard was described again in a 1795 history of St. Saviour's, Southwark: Our readers will remember that, in the account we have given of the Stews on Bank-side, mention is made of a piece of ground, called the Single Woman’s Burying Ground, set apart as the burial place of those unfortunate females; we are very much inclined to believe this was the spot, for in early times the ceremony of consecration would certainly not have been omitted; and if it had been performed, it would doubtless have appeared by some register, either in the possession of the Bishop of Winchester, or in the proper ecclesiastical court.

Its earliest known mention is in an 1833 work by antiquarian William Taylor, who is also the first historian to explicitly state that the modern site on Redcross Street is the same as the "single woman's churchyard" of Stow's era.

However, after the removal of some of the remains to the parish facilities in Brookwood Cemetery, Surrey, the site was covered in warehousing and other commercial buildings, including a timber yard.

[6] One of the most significant Roman archaeological sites ever found in London—including a mausoleum and highly preserved mosaic—was uncovered on the wider plot of land (just outside the boundaries of Cross Bones) in 2022.

[11] In response to the threat of redevelopment, a local group, Friends of Cross Bones, formed in 1996 to campaign to preserve the graveyard and to raise awareness of its historical and cultural significance.

[17][18] Constable claims that his stories were "transmitted" to him by "The Goose," the spirit of a medieval sex worker interred in the graveyard, and from 1998 to 2010 he hosted an annual Halloween "ritual drama" at Southwark Playhouse to honour all those buried there.

In August 2019, singer-songwriter Frank Turner included a song about Cross Bones, called "The Graveyard of the Outcast Dead", on his album No Man's Land.