Po czterech latach od pierwszego koncertu w Warszawie artystka wystąpi dzięki Erze Jazzu. Program „Tribute to Tom Waits” wydany został wcześniej na płycie „Temptation” i przyniósł jej kanadyjską Grammy – nagrodę Juno.
W czasie koncertów Holly Cole tworzy niezwykle intymny nastrój, jej zmysłowy głos jest blisko słuchacza, a zespół towarzyszący subtelnie podkreśla ekspresję interpretacji.
Cole od dziecka była otoczona muzyką, co pozwoliło jej wyrobić sobie smak i odkryć wielu interesujących wykonawców. Jak się okazało, głównie tych z kręgu jazzu. Chociaż nauczyła się grać na fortepianie i okazjonalnie śpiewała, nie widziała się w show-biznesie. Dopiero wizyta u studiującego w Berklee College of Music brata i rozmowy z młodymi, ambitnymi muzykami uświadomiły jej, że właśnie w jazzie może znaleźć własną artystyczną drogę. W 1986 roku tworzyła trio z kontrabasistą Davidem Piltchem i pianistą Aaronem Davisem.
Nagrała pierwszą płytę z nastrojowymi interpretacjami tematów świątecznych „Christmas Blues”, a następnie album „Girl Talk”. Na kolejnym „Blame It on My Youth” wykrystalizował się jej eklektyczny styl. Sięgała do tematów innych wykonawców, śpiewając je w swobodnym, jazzującym stylu. Znajdziemy tam „Purple Avenue” Toma Waitsa, „God Will” Lyle’a Lovetta, piosenki z musicalu „My Fair Lady” i słynny temat „Trust in Me” z filmu Disneya „Księga dżungli”. Szczególnie upodobała sobie utwory Toma Waitsa, bo ich powściągliwy charakter i proste melodie pasowały do jej stylu.
W 1995 roku ukazał się album „Temptation” zawierający wyłącznie jego kompozycje. Przyniósł Cole uznanie na całym świecie i zaproszenia na koncerty, również do Polski.
