A Rolling Stones 1993-as Steel Wheels koncertkörútja után hagyta ott Jaggeréket, hogy hatékonyabban tudjon foglakozni a Sticky Fingers nevű londoni éttermével és több időt töltsön a családjával. Akkor még nem gondolta volna, hogy két év múlva saját csapatában muzsikál. 1995 végén barátjával, Terrry Taylorral még csak otthon pengettek, de az örömzenélés hírére sorra jöttek a régi zenész cimborák, Georgie Fame billentyűs-énekes, Albert Lee gitáros, Peter Frampton, a 70-es évek körülrajongott tinibálványa, Andy Fairwater Low gitáros és Gary Brooker (Ex-Procol Harum), aki a "halványnál is fehérebb árnyalatot" hozta a csapatba. Később mások is beszálltak, de ez nem ment a színvonal rovására.
Az első - Rhythm Kings - nagylemez 1997 őszén került piacra és nagyszerű fogadtatásra talált. Kezdetben kis klubokban tesztelték muzsikájukkal a közönséget, de a tömeget látva egészen felbátorodtak. Wyman úgy érezte magát a sikert látva, mintha egy időutazáson venne részt a Rolling Stones 1962-es 63-as koncertjeinek őrjöngő hangulatát idézte a fogadtatásuk.
A Rhythm Kings idén megjelent Just For A Thrill című lemeze a legkényesebb zenei ízlésűek igényeit is kielégíti. Wyman ismert zenésztársai mellett feltűnik egy új arc is az egyik számban, az egykori Dire Straits gitáros-főnöke, Mark Knopfler.