Costruita dai Cantieri Riuniti dell'Adriatico come risarcimento di guerra italiano al governo greco, entrò in servizio nel 1965, come traghetto Aphrodite.
Successivamente, la piccola compagnia di navigazione greca Sun Lines l'acquisì e nel 1966 fu sottoposta a un restauro completo presso il cantiere navale Mariotti, che ne migliorò il profilo e le conferì un grado di eleganza e modernità capace di elevare gli standard delle navi passeggeri greche dell'epoca.
La compagnia si affidò all'architetto Nino Zoncada per il design d tutte le navi.
La Stella Oceanis aveva una stazza di 6.000 tonnellate e 280 sistemazioni a disposizione dei passeggeri, Il progetto di allestimento elaborato da Zoncada includeva opere d'arte di Emanuele Luzzati ed Enrico Paulucci. Luzzati, in particolare, fece un lavoro straordinario per questa nave altamente sottovalutata. La maggior parte dei suoi pezzi racconta le storie di Omero con una forte inclinazione all'antica simbologia cretese.