After settling in Fenelon Falls, Ontario at the age of three, she grew up in a house rich with experimental art and musical expression. Paul would often make cassettes of rare and eclectic music for his daughter to listen to and her early influences included Carla Bley, Robert Wyatt, and later PJ Harvey. By her teens, she followed in her parents' footsteps by attending the Etobicoke School of the Arts (ESA) to study drama. There she met Amy Millan and Kevin Drew, with whom she would later collaborate in Broken Social Scene (co-founded by Drew), a musical collective. During their time at ESA, Haines and Millan formed their first band together (around 1990), and she also briefly dated Drew.