Первый сценический выход был, как не трудно догадаться, вместе с отцом. В ресторане «Казбек», загримированный под русского слепого певца-сказителя Кудеяра, Баянов проходил с посохом через зал, держась за мальчика-поводыря, у которого в руке была тарелочка для подаяния. Этим мальчиком и была тогда десятилетняя Алла. А в 13 лет она сама уже пела в баре «Казанова», где ее заметил Александр Вертинский. Он пригласил Аллу Баянову петь в своей программе в парижском ресторане «Эрмитаж». И хотя мама весьма противилась этому, заманчивые финансовые предложения сделали свое дело.
У Вертинского в «Эрмитаже», где собирался цвет русской белой эмиграции, настигла её первая любовь. На Аллу обратил внимание красавец князь Андрей Оболенский. После недолгого романа по старому обычаю, он попросил у родителей её руки. Мама, как водится, поблагодарила и дала свое и отцовское согласие, но… через три года, когда «невесте» исполнится 17 лет…
Первая любовь Аллы Баяновой закончилась трагически. Её избранник разбился насмерть в автомобильной аварии. Уже в России, в одном из интервью Алла Баянова заметила: «Будучи княгиней Оболенской, я бы, конечно, никогда не узнала своих русских зрителей. Так, видно, хотела моя звезда….»
А звезда её вела на сцену – на европейскую сцену с репертуаром старинных цыганских песен и русских романсов. Завоевав известность у парижской публики, в конце 1920-х – начале 1930-х годов она работает в самых престижных ресторанах Сербии, Греции, Сирии, Ливана, Палестины. А в 1934-ом году вместе с родителями возвращается в Бухарест, чтобы петь в популярном тогда ночном баре «Лещенко» на одной сцене с Александром Вертинским, Константином Сокольским и самим Петром Лещенко.
В ресторане «Лещенко» Алла Баянова пела почти до начала Второй мировой войны. В одном из интервью она вспоминала: «Понимаете, прежние кабаки очень отличались от нынешних ресторанов. Когда на эстраду выходил артист, официанты не имели права обслуживать посетителей, никто не входил и не выходил из зала. Если подъезжали гости, их просили подождать до конца номера. Сейчас все иначе. Певец выступает, а прямо у него перед носом жуют шашлыки. Я этого не понимаю. Для артистов моего поколения выступления в ресторанах было настоящей школой». Такую школу проходила Алла Баянова перед тем как выйти на эстрадную сцену.