Hindley a été de plus en plus attirée par l’Église catholique après elle ait commencé au Ryder Brown Secondary Modern, et a commencé à aller au catéchisme pour rentrer dans l’Église peu après l’enterrement de Higgins. Elle a pris le nom de confirmation Veronica, et a reçu sa première communion en novembre 1958. Elle est aussi devenue la marraine du neveu de Michael, Anthony John. C’est également à ce moment que Hindley a commencé à se peroxyder les cheveux.
Le premier travail de Hindley était en tant employée dans une société d’électrotechnique locale. Elle faisait des courses, faisait du thé, et tapait à la machine. Elle était bien aimée dans l’entreprise, assez pour que lorsqu’elle a perdu sa paie de la première semaine, les autres filles ont fait une quête pour la remplacer. Elle a eu une courte relation avec Ronnie Sinclair dès Noël 1958, et se sont fiancés à l’âge de 17 ans. Les fiançailles ont été rompues plusieurs mois plus tard ; Hindley trouvait apparemment Sinclair immature, et incapable de lui fournir la vie qu’elle imaginait pour elle.
Peu après son 17ème anniversaire, elle a changé sa couleur de cheveux. Elle a pris des leçons de judo une fois par semaine dans une école locale, mais a trouvé que ses partenaires ne voulaient pas s’entraîner avec elle, puisqu’elle était lente à relâcher sa prise. Elle a trouvé un travail à Bratby et Hinchliffe, entreprise technique de Gorton, mais a été renvoyée pour absentéisme au bout de six mois.
En 1961, Myra Hindley a rejoint à 18 ans Millwards en tant que secrétaire. Elle s’est rapidement entichée de Brady, malgré avoir appris qu’il avait un casier judiciaire. Elle a commencé à tenir un journal et, bien qu’elle a eu des rendez vous avec d’autres hommes, certaines entrées détaillent sa fascination pour Brady, à qui elle a finit par parler pour la première fois le 27 juillet 1961.

Durant les mois qui ont suivi, elle a continué à écrire, et s’est désillusionnée pour lui, jusqu’au 22 décembre où Brady lui a demandé de sortir avec lui au cinéma, où ils ont regardé un film sur le procès de Nuremberg. Leurs rendez vous suivaient un modèle régulier ; cinéma, habituellement un film d’adulte, et puis retour chez Hindley pour boire du vin allemand. Brady lui a alors donné de la lecture, et le couple passait leur repas au travail à se lire à voix haute des récits sur les atrocités nazies.