Finita quella vicenda, Domino riprese a viaggiare, in particolare in Europa, guadagnandosi la fama di eterna vagabonda. Le prime umili esibizioni dal vivo misero a punto un'arte sofisticata di canto esistenziale accoppiato ad arrangiamenti ballabili. Il primo documento sonoro fu l'EP East And West (Crepuscule, 1984 - LTM, 2004). Liricamente perduta nel suo universo interiore, poetessa decadente in preda a fantasie romantiche, Domino si trastulla con il rhythm and blues sincopato e sonnambulo di With The Day Comes The Dawn, con l'esotismo robotico di Review e con il funk soffice e ipnotico di Trust In Love (singolo del 1983). La lezione della new wave e della no wave americane sono ancora molto forti, anche se mediate da uno spirito mitteleuropeo (soprattutto nella tenera ballad Everyday I Don't).

Nel 1986 usci` il primo album, Anna Domino (Les Disques Du Crepuscule, 1986 - LTM, 2004), comprendente i singoli Rhythm (1984) e Take That (1985) e Summer (1986). Anna Domino cantava come una chanteuse degli anni '20, immersa in fumose atmosfere jazz e blues, accompagnata da un combo ridotto ai minimi termini.

L'anno dopo This Time (Crepuscule, 1987 - LTM, 2004) segno` un'improvvisa quanto maldestra conversione al synth-pop, forse anche per colpa del polistrumentista Michel Delory. Domino si divincola fra funk da discoteca (Time For Us) e musica new age (Lake).

Recuperando un po' della sua personalita`, Domino fuse con maggior convinzione le sue propensioni per la musica nera e l'elettronica atmosferica del compagno sull'EP Colouring In The Edge And The Outline (Giant, 1990), in particolare nella latineggiante Perfect Day e 88.

Mysteries Of America (Les Disques Du Crepuscule, 1990 - LTM, 2004) torna al sound spartano e fantasma degli esordi, alle superbe armonie jazz, alle cantilene infantili del primo album. Domino non e` un gran che' di cantante o un gran che' di compositrice e la sua unica chance di superare i suoi limiti sta negli arrangiamenti; quando sballa quelli, le sue canzoni si afflosciano tiepide e insipide.

Favorite Songs From The Twilight Years (Cartunes, 1997) e` un'antologia della carriera.