Lewis byl vybrán na 23. místě draftu 1996 týmem San Jose Clash. V San Jose hrál čtyři roky, od druhé sezony nastupoval pravidelně v základní sestavě. V březnu 2000 podepsal smlouvu s druholigovým anglickýmFulhamem. V sezoně 2000/01, kdy Fulham postoupil do první ligy, odehrál 7 zápasů a v sezoně 2001/02 odehrál pouhé jedno utkání. V roce 2002 přestoupil do Prestonu, kde hrál tři roky a nastoupil zde do více než 100 ligových utkání. V červnu 2005 se stal volným hráčem a podepsal smlouvu s Leeds United FC. V Leeds začínal jako levý obránce, po pár utkáních se vrátil na svoji oblíbenou pozici – křídelního hráče. Na konci sezony 2006/07 získal cenu fanoušků pro nejlepšího hráče Leeds a stal se čtvrtým zahraničním hráčem, který tuto cenu dostal. V roce 2007 podepsal dvouletou smlouvu v Derby, už na začátku sezony 2008/09 se domluvil na ukončení spolupráce a návratu do MLS. V srpnu 2008 podepsal v Los Angeles Galaxy, kde se potkal s trenérem Arenou, který Lewise vedl u reprezentace. Po dvou a půl letech oznámil, že po sezoně 2010 ukončí kariéru.