In 1983, she travelled to Toronto to seek a musical career. In 1986, she founded a trio with bassist David Piltch and pianist Aaron Davis. Offered a record deal in 1989, the Holly Cole Trio released an EP, Christmas Blues, that year, which featured a striking version of The Pretenders' "2,000 Miles". This was followed by their first full album, Girl Talk, in 1990.
A succession of releases through the early 90's fleshed out the trio's musical daring. For example, 1991's Blame It On My Youth, covers songs by Tom Waits ("Purple Avenue", aka "Empty Pockets"), Lyle Lovett ("God Will"), includes show tunes such as "If I Were a Bell" (from Guys and Dolls) and "On the Street Where You Live" (from My Fair Lady), and even remakes "Trust In Me", a silly song from Disney's The Jungle Book, into a sultry and sinister song of seduction. Also recorded in this period was a remarkable reinterpretation of Elvis Costello's "Allison".
Following 1993's Don't Smoke In Bed, the trio took on its most audacious effort, a CD entirely of songs by Tom Waits, called Temptation. This 1995 release also dropped the "Trio" from the label.