Miller-Heidke ble uteksaminert fra St Aidan's Anglican Girls' School i 1998, og tok senere en bachelorgrad i musikk og klassisk sang ved Queensland Conservatorium of Music, etterfulgt av en mastergrad i musikk ved Queensland University of Technology. Som klassisk sanger har hun vunnet flere priser, inkludert Elizabeth Muir Prize (2000), Donald Penman Prize (2001), Linda Edith Allen Memorial Prize (2002) og Horace Keats Prize (2002). Hun har opptrådt i Orpheus in the Underworld (2000), Venus og Adonis (2002) og The Pilgrim's Progress (2002).[3][4]
Miller-Heidke spilte i flere band i Brisbane før hun startet som soloartist i 2002. I 2006 skrev hun kontrakt med Sony Australia,og slapp sin tredje EP, Circular Breathing, samme år, etterfulgt av debutalbumet Little Eve 15. juni 2007. Albumet ble sertifisert med gull i Australia.[5] Miller-Heidkes andre album, Curiouser, ble sluppet i Australia 18. oktober 2008.