Après avoir quitté Epic Records au début des années 1980, Billy Ocean signe chez Jive Records et fait équipe avec le producteur Keith Diamond. Ils coécrivent plusieurs chansons dont Caribbean Queen et enregistrent l'album Suddenly à New York[2].
Le titre original de la chanson est g.u, un acronyme familier qui désigne un californien tombant amoureux d'une new-yorkaise, mais pour sa sortie au Royaume-Uni durant l'été 1984, il est modifié en European Queen (No More Love On The Run). Malheureusement, la chanson passe complètement inaperçue. Pas découragé, Billy Ocean décide de sortir une version plus disco de la chanson et la rebaptise Caribbean Queen. Au studio, il laisse les couplets tels quels et réenregistre simplement les refrains. Un membre du label Jive Records lui propose également de sortir une troisième version intitulée African Queen[2].
Échaudée par l'échec britannique, Jive Records laisse de côté European Queen et préfère sortir Caribbean Queen aux États-Unis. Le succès est immédiat et permet à Billy Ocean de faire son entrée à la 85e position du classement américain des meilleures ventes de 45 tours, ce qui ne lui était pas arrivé depuis Love Really Hurts Without You en mai 1976. Douze semaines plus tard, la chanson atteint le sommet du classement, ce qui constitue une première pour Billy Ocean ainsi que pour son label, Jive Records. La chanson reste en tête des ventes pendant deux semaines consécutives[2].