Aida Vedishcheva was born in Kazan (administrative center of Tatar ASSR) in the doctor's family of scientist, professor of dentistry Solomon Weiss and surgeon Elena Emelyanova, who arrived from Kyiv just before World War II.
In 1951, the Ministry of Health offered professor Weiss to open faculty of therapeutic dentistry in Irkutsk, Siberia.
Aida Vedishcheva began her singing performance career in the early 1960s, in Orel State Philharmonic Society.
She achieved the national recognition after singing "Song About Bears" in 1967 for the movie Kidnapping, Caucasian Style (seven and a half million records were sold).
With the song "Comrade" (1970), Vedishcheva won the 1st prize on the competition at the Moscow radio station "Youth".
[citation needed] Despite her great success among the listeners, she met numerous obstacles from the Soviet officials.
One of the reasons was the anti-Semitism politics of Sergey Lapin,[2] the chairman of All-Union Radio as well as her unauthorized performance in Sopot Festival shortly after the events of the Prague Spring (after which she was blacklisted by the USSR Ministry of Culture).
She enrolled in Brooklyn College, taking a course of theater program, where she studied American history of Hollywood, Broadway, cinematography, and dance.