Sebestyén was born Budapest. 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 is a founding member of Hungarian folk group Muzsikás. She is known for adaptations of Somogy and Erdély folk songs, some of which appear in Deep Forest's Boheme album, which received the Grammy Award for Best World Music Album in 1996. She has also adapted Hindi, Yiddish, Serbian, Bulgarian, Slovak folk songs into traditional Hungarian style. She sang in and contributed material to the album Kaddish by Towering Inferno (Richard Wolfson and Andy Saunders, 1993). She also sang "Rivers" on the multiple artist album Big Blue Ball released in 2008.
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"). Costa-Gavras' 1989 film Music Box featured the opening half of Sebestyén's song "Mária altatója".
As primary artist
- Apocrypha (1992, Hannibal)
With Andy Irvine and Davy Spillane
- East Wind (1992, Tara)
With various artists
- The Rough Guide to the Music of Eastern Europe (1999, World Music Network)
- Big Blue Ball (2008, Real World, Rykodisc)
- Omohide Poroporo Orijinaru Saundotorakku - Only Yesterday Original Soundtrack
- "Hungarian folk singer Sebestyen UNESCO Artist for Peace". culture.hu. Hungarian Ministry of National Resources. 2 June 2010.