Na Festiwalu w Opolu w roku 1967 wystąpiła w debiutach piosenką Rurka z Kremem śpiewaną przy wtórze Alibabek. Debiuty wygrał wówczas inny Kresowiak Czesław Niemen piosenką Dziwny jest ten świat. W 1969 roku ukończyła studia we Wyższej Szkole Pedagogicznej w Łodzi i podjęła współpracę z powstającym właśnie zespołem Quorum, w którym śpiewała przez rok.
Norwegia W 1970 roku poślubiła norweskiego reżysera filmowego i polonofila Haakona Sandøya, z którym wyjechała do Norwegii. Tam zadebiutowała w roku 1977, gdy jako pierwsza wprowadziła na norweską scenę funk rocka. Zdobyła najwyższą nagrodę norweskiego świata muzycznego Spellemannprisen (w kategorii pop) za dwie płyty Alex i Handle With Care, które szybko uzyskały status złotych. Popularność Aleksandry Naumik pozwoliła na międzynarodową współpracę ze sławnymi muzykami. Podpisawszy kontrakty z Polygram International (obecnie Universal) i RCA Records miała otwartą drogę, by śpiewać u boku Davida Fostera, Mike’a Hursta, Andraé Croucha, Andy’ego Summersa i Glena Matlocka. Dwudziestomilionowa publiczność mogła ją podziwiać w niemieckim programie telewizyjnym Musikladen, oglądanym aż w 18 krajach. U szczytu kariery narzucała popkulturowe trendy, a określenie fryzura na Alex (Alex-hår) jest do dziś w powszechnym użyciu.