Andy Paul (oik. Andreas Pavlou) eli lapsuutensa ja nuoruutensa Isossa-Britanniassa, vaikka onkin syntyperäinen kyproksenkreikkalainen nappisilmä. Musikaalisuus ilmeni hänessä jo varhain ja Andyn suurimmat idolit olivat Elvis, Cliff Richard, Tom Jones ja Engelbert Humperdinck. Laulamisen ohessa nuorukainen kirjoitteli myös omia kappaleita. Ura musiikin parissa sai lähtösysäyksen Andyn osallistuttua talent-kilpailuun. Hän esitti kisassa lapsuudensuosikkiaan Elvistä niin vakuuttavasti, että voitti ensimmäisen palkinnon. Palkintona oli esiintymissopimus, jonka pohjalta Andy pääsi esiintymään eri puolilla Britanniaa saaden arvokasta esiintymiskokemusta.
1980-luvun alussa Andy levytti ensimmäisen kappaleensa "Heartbreak situation" silloin vielä tuntemattoman tuottajakolmikon Stock-Aitken-Watermanin kanssa. Levy jäi kuitenkin todella vähäiselle huomiolle. Vuonna 1984 Andy lähetti oman kappaleensa "Anna Mari Elena" Kyproksen euroviisukarsintoihin. Kirjavassa neljän kappaleen karsinnassa toiselle sijalle jäi Anna Vissin sisko Lia, joka kylläkin pääsi edustamaan Kyprosta heti seuraavana vuonna. Kolmanneksi sijoittui Yiannis Demetriou kappaleella "Thimame". Merkittävää on, että Yiannis lähetti saman laulun Kyproksen karsintaan myös vuonna 1988 ja voitti sen. Laulun alkuperä tuli ilmi liian myöhään ja lopulta Kypros joutui vetäytymään vuoden 1988 viisuista kokonaan. Vuoden 1984 karsintojen jumboksi jäi Jimmy Makoulis, joka oli edustanut Itävaltaa jo vuonna 1961.
Kepeä popkappale "Anna Mari Elena" ei kuitenkaan purrut Luxemburgissa kansainvälisiin tuomaristoihin, vaan Andyn oli tyytyminen 15:sta sijaan. Jugoslavian raadin mielestä Kypros tosin oli paras kaikista ja Tanskan raadinkin mielestä toiseksi paras, mutta ikävä kyllä Ruotsia, Ranskaa ja Irlantia lukuunottamatta kaikki olivat täysin eri mieltä ja rakas naapuri Kreikkakin loisti näissä kisoissa poissaolollaan. Stock-Aitken-Waterman tuotti edustuskappaleen levyversion ja siitä sukeutui pieni hitti Euroopassa. Andy Paul on jatkanut uraansa tuotteliaana, mutta ikävä kyllä ei kovin menestyvänä eturivin artistina.