Saksofonistit Markus Holkko ja Timo Lassy alkoivat vuonna 2000 järjestää Uudenmaankadulla sijainneessa treenikämpässä jameja, joissa lopulta syntyi paljon kiitosta kerännyt Uudenmaankadun All Stars, myöhemmin U-Street All Stars. Bändillä oli kunnianhimoiset tavoitteet alusta alkaen, ja se lähti rakentamaan yhteistä bändisoundia pitkäjänteisellä otteella. Soundiksi muodostui blues-fiilis ja rytmisesti vanhva svengi, joka oli 2000-luvun alussa Suomessa vielä vierasta.

U-Street All Stars teki pohjatyönsä hyvin ja oli kentälle tullessaan harvinaisen valmis, energinen, tiukka ja persoonallinen. Heinäkuussa 2001 yhtye voitti Espanjassa Getxon jazzbändikisan sekä tuomari- että yleisöäänestyksen, ja Markus Holkko oli myö yleisön solistisuosikki. Vuonna 2002 alkoi U-Street All Starsin toiminaan intensiivisin kolmevuotisjakso. Maaliskuussa bändi teki Jazzliiton kiertueen ja kesäkuussa ilmestyi debyyttialbumi Helsinki Sessions (Blue Note 2002). Levystä nousi arvostelumenestys ja se oli julkaisuvuotensa Jazz-Emma -ehdokas. Samana vuonna yhtyeelle myönnettiin Suomen arvostelijain liiton Kriitikin kannukset sekä Pori Jazzin Vuoden nuori taiteilija -tunnustus, johon liittyen yhtye soitti festivaalin päälavalla Kirjurinluodolla.

Yhtyeelle on vuosien varrella kertynyt keikkakokemusta niin Yhdysvaltojen, Euroopan kuin kotimaankin suurilta jazzfestivaaleilta. Vuonna 2004 julkaistu toinen albumi Bowling (Blue Note) oli ensimmäisen lailla menestys ja keräsi paljon kiitosta kriitikoilta.

U-Street All Stars vetäytyi muiden soittokiireidensä vuoksi loppuvuonna 2005 keikkatauolle, joka on jatkunut näihin päiviin asti. Bändiä ei kuitenkaan ole kuopattu lopullisesti, vaan yhtye on jäsentensä mukaan vain "telakalla", joten toivotaan, että yleisö saisi vielä nauttia kokoonpanon tasokkaasta menosta tulevaisuudessakin.