Formati nel 1981, dopo un primo EP pubblicarono il singolo Death And The Maiden (1984), con un minuto di assolo d'organo stonato che sembra parodiare In A Gadda Da Vida degli Iron Butterfly o la Light My Fire dei Doors. L'EP Ten O'Clock In The Afternoon (Flying Nun, 1985) e` il loro manifesto artistico: Joed Out dichiara apertamente il loro amore per il beat, quello incontaminato dei primi anni '60, ma le sonorita` ruvide e spavalde di Baud To Tears lasciano anche intuire che il punkrock non e` passato invano (ne` tantomeno Elvis Costello). L'incedere spigliato di You Say You fa pensare ai Feelies, ma con un'infiltrazione di eventi atonali qua e la`. Il vero capolavoro e` Burlesque, che spezza il ritmo in continuazione senza mai perderlo e inframezza un assolo d'organo fiacco e fuori tempo. Downes riforma il pop in maniera piu` radicale di quanto facciano i Chills o i Clean, e per questo sara` punito con una emarginazione piu` lunga. I primi singoli ed EP verranno raccolti su Juvenilia (1987).

Sull'album Halleluja All The Way Home (Slash, 1985) fa la sua comparsa l'oboe di Downes; ma si tratta di un disco di transizione, che non sfrutta appieno le intuizioni dell'EP.

A spingersi piu` avanti e` semmai Bird-Dog (Slash, 1987), nel quale le canzoni sono si` semplici e dimesse, di una malinconia che va oltre il crepuscolare e lambisce patologie da manicomio, ma al tempo stesso sono ciascuna abbellita da uno strumento (a fiato, ad archi, pianoforte) piu` nobile del convenzionale trio rock. Sommata ai ritmi sempre un po' obliqui (merito del batterista Robbie Yeats), tanto dimessi che dovrebbero essere trascurabili, ma tanto irregolari che finiscono per essere protagonisti, e sommata alle liriche coltissime, questa trovata ha un effetto quasi "straniante". Cosi` Makes No Difference avanza fiacca e insicura, ma e` punteggiata da un corno e un'armonica; il ritornello frizzante di Dippy's Last Trip e` propulso da un pianoforte da saloon; i fagotti incalzano la novelty alla Bonzo Dog Band di Icarus Missed; fino al gran finale di C.D. Jimmy Jazz And Me, una filastrocca alla Richman che pure sfodera quasi un'intera orchestra e di conseguenza tutta una serie di metamorfosi sinfoniche.
L'effetto piu` suggestivo, per quanto quasi imbarazzante, e` quello del coro femminile da anni '50 (la bassista Jane Dodd piu` Caroline Easther), impiegato ad arte in You Forget Love, uno dei suoi beat innocenti, e in Just Mum, una predica affettuosa da timido adolescente (ma con testi degni di un saggio filosofico). Il suo crooning impazzito sulle cadenze febbrili alla Feelies di Slow Sad Love Song, la ninnananna a passo di valzer di Only Dream Left, la cantilena infantile sul cadenzato rhythm and blues della title-track ne fanno un genio della musica capace degli accostamenti piu` audaci.

Meno versatili ed eccentrici, il successivo Some Disenchanted Evening (Flying Nun, 1990), con Jesus What A Jerk e The Funniest Thing Ready To Fly (Slash, 1991), con la squisita Tremble, Gloom Junky e Such As I (ma anche con qualche arrangiamento orchestrale di troppo), non riusciranno a ripetere quel miracolo, anche se poco a poco conferiranno a Downes lo status di cantautore piu` erudito della Nuova Zelanda.

Way Out Where (Slash, 1993), che aggiunge una seconda chitarra alla line-up, segna invece il ritorno a uno stile piu` spontaneo, quasi rock and roll, e sfodera un paio dei loro brani piu` riusciti: Mission Of Love e I Stare Out.

Nel 1994 Downes si e` laureato con una tesi su Mahler.

Over The Moon (Sony, 1996) was the last Verlaines album.

In 1999 Graeme Downes composed, played and recorded Hammers And Anvils (Matador, 2001). The dramatic crooning of Hammers And Anvils, the chaotic tension of Cattle Cars And Chainsaws, the nervous blabbering of Day Of The Dead, the epic desperation of Rock'n'Roll Hero best display Downes' intrepid albeit insecure persona. His half-baked attempts at pop (whether the Beatles-ian kind, as in Alright By Me, or the romantic kind, as in Shoreleaves and Mastercontrol) tend to fall flat, but his take on the tradition of show-tunes (January Song, Getting Out Of It) and the tradition of 1970s' folksinger (Song For A Hollywood Road Movie could be a Joni Mitchell rarity) Downes' skills as storyteller are intact. He can deliver a story with passion, anger, regret, scorn, humour and jump from one mood to the other with elegant nonchalance. The Verlaines are occasionally missed when the song comes through as too "thin", fragile, incomplete. Witness the difference a real arrangement makes in Rock'n'Roll Hero, a powerful mini-epic and one of the standout songs of Downes' career.