This story is equal parts American Dream and Russian fairy tale. Once upon a time in the late 1980s, in the dark days of communism, a 9-year-old girl named Regina Spektor left her home in the bad, old Soviet Union and came to America – to the Bronx, specifically – with her parents. Plenty of relatives and friends, all Russian Jews, were leaving for America at the same time or would be soon, so the little girl was saddest about leaving behind her old brown Petrov piano, the one her late grandfather had given to her mother. She worried about not being able to continue her classical piano lessons in her new home.

Luckily for us, young Regina found a new piano, and this week, 16 years after leaving Russia, the singer-songwriter, pianist, and alternative chanteuse appeared as the featured musical guest on “The Tonight Show with Jay Leno.” And everyone lived happily ever after.

Ms. Spektor was born in 1980 in Moscow to musician parents. They were also practicing Jews, not a great thing to be in the U.S.S.R. at the time. So in 1989, Ms. Spektor’s family joined the several waves of Russian Jews to flee anti-Semitism in the former Soviet Union in the 1970s and ’80s. After several months in refugee camps and housing in Austria and Italy, the Spektors arrived in New York City in August 1989 and moved into the Bronx apartment the 25-year-old up-and-coming balladeer still shares with her parents and 14-year-old brother, Bear.

“My parents wanted religious freedom,” Ms. Spektor explained. “The fact that I’m Jewish is definitely one of the most important, defining things in my life. Not necessarily the religion, but the ethnicity. I was aware of it when I was very young – having certain customs in the family, always knowing in Russia that I was different, then the whole immigration process. We were among the first Russians in the Bronx. There were really funny newspaper articles about us. It was just a big strange thing, but we became part of the Jewish community there and people there were really helpful in a lot of ways.”

Many of the Spektors’ friends and associates from the Moscow Jewish community also settled in the tri-state region. As for family, Ms. Spektor’s paternal grandparents and an uncle were refuseniks, the term for Russian Jews in the 1970s and ’80s who were long refused exit visas because of their religion. As the Soviet Union disintegrated in the early 1990s, they finally got out and arrived in New York.

At first the family couldn’t afford music lessons for Regina, but one night after working the late shift at a photo developing company to help pay the bills, her father struck up a conversation on the subway with a man carrying a violin case. It turned out the man was a concert violinist who attended the same synagogue as the elder Spektor, and that his wife, Sonia Vargas, was a professor of piano at the Manhattan School of Music.

“They invited us to their house to play duets for us,” Ms. Spektor said. “We were very excited because it was our first concert since we left Russia. After they were done playing their program, I asked her if she would be my piano teacher. My mom turned beet red because we couldn’t afford it and I was being rude. But I didn’t care about being rude, and Sonia said, ‘Of course,’ and she taught me. She wouldn’t take anything from us, and even when we could pay, they didn’t take anything. Their whole family became like godparents to me.”

After many lessons, and her discovery of popular music, Ms. Spektor attended SUNY Purchase, studied music, and began her performing career in campus venues before recording her first CD of original songs in the university’s studios. “11:11” was released in 2001. After graduation, Ms. Spektor started appearing at open-mic nights downtown before emerging as a performer allied with the anti-folk scene centered in the East Village and the Lower East Side. Sidewalk Cafe and the Living Room (in its original, thumbnail-size incarnation) became her second homes as she accrued a devoted downtown following. Her second album, “Songs,” which contained the plaintive standout track “Samson,” arrived in 2002.

Citing Mozart and Bob Dylan as two major influences, Ms. Spektor mixes cultural as well as stylistic metaphors to great effect. Her lyrics are populated by a jumble of multi-sourced characters, situations, and emotions, as evidenced by some titles from her most recent album, “Soviet Kitsch,” just released by Sire Records: “Ode to Divorce,” “Poor Little Rich Boy,” “Ghost of Corporate Future,” and “Carbon Monoxide.” Her often ethereal, sometimes guttural, occasionally ululating vocal delivery has garnered her comparisons to Joni Mitchell, Tori Amos, and Ani DiFranco, comparisons she feels alternately honored and annoyed by – “Oh, it’s a woman singing solo with a piano. She’s the new Tori Amos.”

After years of captivating small audiences in downtown New York venues, in 2003 Ms. Spektor toured America with her friends the Strokes. Her understated, lyrical live act might seem a mismatch with the Strokes’ gritty style, but the tour was a success: not only did it toughen her up to raucous crowd reactions, it introduced her to a huge new audience – which is only getting bigger.