Sebestyén was born in Budapest, Hungary.[1] Her mother is a composer, and was a music student of Zoltán Kodály. Her father was an economist and author. When Sebestyén was seven years old, her father, returning from a trip to the U.S. as a visiting professor (under a grant from the Ford Foundation), brought home a large collection of ethnic music recordings from the Smithsonian Institution. Sebestyén was educated at Miklós Radnóti Grammar School, Budapest.
Sebestyén's song "Szerelem, szerelem", performed with Muzsikás, featured in the movie The English Patient (1996). Three more songs she recorded with Muzsikás appeared in the Japanese anime film Only Yesterday (1991) by Studio Ghibli: "Teremtés" ("Creation"), "Hajnali nóta" ("Morning Song"), and "Fuvom az énekem" ("I Sing My Song").[2] Costa-Gavras' 1989 film Music Box featured the opening half of Sebestyén's song "Mária altatója".
Ivor Cutler was a fan of Sebestyén, citing her influence on several occasions, most notably in an article for The Guardian newspaper in January 2004.[4] Cutler selected two of her songs for a CD (Cute, eh?) released in 1999 containing his favourite musical tracks.[5] Cutler also chose songs by Sebestyén for his 1991 BBC Radio series, Cutler the Lax.[6]