24 września 1958 roku Flo Sandon’s i Natalino Otto odkryli w jednej z sal tanecznych Cremony młodą solistkę, Annę Marię Mazzini, umożliwiając jej następnie debiut płytowy. W tym samym roku Flo Sandon’s wygrała pierwszą edycję Burlamacco d’Oro. W 1959 wydała afrykańskie pieśni rytualne, spopularyzowała dwie znane piosenki południowoamerykańskie „Pani” i „Galopeira”, wylansowała również kilka włoskich piosenek: „Il tuo sorriso” i „Concertino” Gorniego Kramera oraz „Arrivederci” Umberta Bindiego. Podczas świąt Bożego Narodzenia 1959 roku wyruszyła wraz z mężem w długą trasę koncertową, obejmującą takie kraje jak: Szwecja, Norwegia, Filipiny, Dania, Holandia i Anglia. W 1960 roku ponownie wystąpiła na Festiwalu w San Remo, tym razem z piosenką „A come amore”; w czerwcu tego samego roku wygrała Festiwal Piosenki Neapolitańskiej śpiewając piosenkę „Serenata Margelina”.