Läpimurto bluesvaikuteisilla albumeilla
Vuodesta 1993 alkaen Wilson muutti suuntaansa ja tulkitsi akustisia, bluesvaikutteisia kappaleita Blue Note -levymerkillä. Mukana oli omia sävellyksiä sekä covereita artisteilta kuten Robert Johnson, Van Morrison ja Joni Mitchell. Muutos kannatti: kriitikot ylistivät hänen tyylillisesti rohkeaa linjaansa. Wilsonin ensimmäistä Blue Note -albumia Blue Light ’til Dawn (1993) pidetäänkin usein hänen musiikillisena läpimurtonaan.
Vuoden 1995 New Moon Daughter voitti Grammy-palkinnon parhaasta jazzvokaalisuorituksesta. Kaksi vuotta myöhemmin Wilson sai lisää kiitosta esiintyessään Wynton Marsalisin Pulitzer-palkitulla Blood on the Fields -albumilla. Hän teki myös merkittäviä yhteistyöprojekteja Dave Hollandin ja The Rootsin kanssa. Vuonna 1999 hän kunnioitti suurta vaikuttajaansa Miles Davisiä tribuuttialbumilla Traveling Miles.
Vuonna 2001 hän esiintyi Frank Ozin ohjaamassa, Robert De Niron ja Marlon Brandon tähdittämässä rikoselokuvassa Valtikka. Wilson esitti elokuvassa jazzklubin laulajaa.
Vuoden 2002 Belly of the Sun -albumilla Wilson jatkoi laaja-alaisia covervalintojaan, tulkiten kappaleita muun muassa Robbie Robertsonilta ja Jimmy Webbilta. Hän jatkoi myös oman musiikin säveltämistä, kirjoittaen puolet vuoden 2003 Glamoured-albumin kappaleista. Aina luovasti uteliaana hän kokeili hip hop -tekniikoita ja sampleja vuoden 2006 Thunderbird-levyllä. Sen jälkeen hän palasi jazzstandardeihin vuoden 2008 Loverly-albumilla, joka toi hänelle toisen Grammy-palkinnon. Vuonna 2010 ilmestyneellä Silver Pony -albumilla hän yhdisti covereita ja omia kappaleita; mukana vierailivat muun muassa Ravi Coltrane ja John Legend.
Wilson vaihtoi jälleen suuntaa Another Country -albumillaan, joka koostui pääasiassa omista kappaleista ja jonka hän tuotti yhdessä sähkökitaristi Fabrizio Sottin kanssa. Albumi äänitettiin Italiassa, New Orleansissa ja New Yorkissa, ja se julkaistiin kesällä 2012. Vuonna 2015 Wilson siirtyi Sony-yhtiölle ja julkaisi Billie Holiday -tribuutin Coming Forth by Day, jonka tuotti Nick Launay, (tunnettu muun muassa Yeah Yeah Yeahsin ja Nick Caven tuottajana). Levyllä häntä säesti muusikoita yhtyeestä Nick Cave and the Bad Seeds. Seuraavina vuosina Wilson jatkoi aktiivisesti konsertointia, muun muassa entisen Hothouse Flowers -laulajan Liam Ó Maonlaín kanssa, sekä kiersi maailmaa oman yhtyeensä kanssa.
