Absolwentka Kierunku Andragogika Wydziału Psychologii i Pedagogiki Uniwersytetu Warszawskiego, w 1974 roku zaprezentowała się szerszej publiczności w programie telewizyjnym pt. „Miłość ci wszystko wybaczy” złożonym z piosenek Hanki Ordonówny. Dzięki temu występowi Alicja Majewska została zauważona przez środowisko artystyczne, a także przez Mariusza Waltera – redaktora naczelnego Redakcji Widowisk Publicystycznych i Form Dokumentalnych Studia 2 Telewizji Polskiej, który zaproponował artystce przygotowanie programu w stylistyce retro. Do 1977 roku była związana z Teatrem na Targówku w Warszawie, a na lekcje śpiewu uczęszczała do prof. Olgi Łady.

Koncertowała niemal we wszystkich krajach Europy, Azji, Ameryki i w Australii. Wylansowała szereg przebojów, m.in. „Jeszcze się tam żagiel bieli”, „Odkryjemy miłość nieznaną”, „Być kobietą” czy „Marsz samotnych kobiet”. Zdobywczyni Grand Prix na międzynarodowych Festiwalach w Hawanie i Rostocku, a także wielu nagród, m.in. Krajowego Festiwalu Piosenki Polskiej w Opolu. W 2015 roku została uhonorowana Złotym Mikrofonem – najwyższym odznaczeniem Polskiego Radia przyznawanym osobom, których działanie przyczynia się do utrzymania wysokiego poziomu, rozwoju i popularyzacji radia publicznego oraz za wybitne osiągnięcia twórcze dla radia publicznego.

Dokonała wielu nagrań archiwalnych dla Polskiego Radia i płytowych, owocem których są niezapomniane piosenki wykonane solo, jak i m.in. z Haliną Frąckowiak, Dorotą Osińską, Grzegorzem Markowskim, Jerzym Połomskim, Ryszardem Rynkowskim, Zbigniewem Wodeckim i Andrzejem Zuchą. Śpiewała ponadto w oratoriach Włodzimierza Korcza i Ernesta Brylla.

Śpiewa teksty znakomitych autorów, głównie Wojciecha Młynarskiego. Na stałe współpracuje z kompozytorem i pianistą Włodzimierzem Korczem, autorem muzyki większości jej piosenek, z którym już we wtorek, 6 maja 2025 przyjedzie do Filharmonii im. Mieczysława Karłowicza w Szczecinie na swój „Jubileusz 50 lat! Największe przeboje”.