No universo, foi porque o grupo está sediado no edifício de Vastra, Paternoster House. Não há nenhuma indicação especial de que ela mesma tenha nomeado a propriedade.
Fora do universo (de acordo com um artigo na Doctor Who Magazine) o nome deriva, um tanto circularmente de um artigo do livro de referência da BBC sobre o grupo:
Steven Moffat derived the name Paternoster Gang from The Brilliant Book 2012 where Clayton Hickman referred to their base as Paternoster Row. (DWM 480)