Το 1956, η Μαρινέλλα μπήκε στο Στρατιωτικό Θέατρο Θεσσαλονίκης ως τραγουδίστρια γιατί της έδιναν καλύτερη αμοιβή.
Παράλληλα, ξεκίνησε την καριέρα της ως τραγουδίστρια στο κέντρο «Πανόραμα» της Νέας Ελβετίας Θεσσαλονίκης, πίσω από το γήπεδο του Άρη.
Εκεί, ο Τόλης Χάρμας γνώρισε την Κυριακή Παπαδοπούλου, τη βάπτισε καλλιτεχνικά «Μαρινέλλα», εμπνευσμένος από το ομώνυμο τραγούδι του.
Εκεί, δούλευε μπουζουξής ο Στέλιος Ζαφειρίου, ο άνθρωπος που τη σύστησε στον Στέλιο Καζαντζίδη, ο οποίος είχε εντυπωσιαστεί με τη φωνή της όταν την είχε ακούσει να τραγουδάει.
Ο Στέλιος Καζαντζίδης είχε πάει στο κέντρο προκειμένου να συναντήσει τον Ζαφειρίου, την άκουσε να τραγουδάει ένα τραγούδι που εκείνος είχε πει λίγο νωρίτερα στη δισκογραφία, το τραγούδι «Το πιο πικρό ψωμί» του Γιώργου Μητσάκη.
Όταν η Μαρινέλλα τελείωσε το τραγούδι, ο Ζαφειρίου τη σύστησε στον Καζαντζίδη και τα υπόλοιπα ήταν ιστορία...