De regreso a Londres, se entregó en cuerpo y alma a la música. En casa de Stewart había una buena colección de discos de Al Jonson y de otros famosos cantantes americanos. El artista inglés llegó a conocerlos de memoria: "Pasábamos largas tardes escuchando estos discos. Lo hacíamos por el deseo de descubrir todos los trucos de los cantantes. Me gustaba como pronunciaban las palabras, como las susurraban y las gritaban creando una atmósfera. Era fantástico". La educación musical de Stewart prosiguió escuchando discos de countty y blues; artistas como Ramblin' Jack Elliott y Big Bill Broonzy ejercieron una gran influencia sobre él. Estamos a principios de los sesenta en aquel período Londres era la gran fragua de blues, en la que despuntaron los talentos de The Rolling Stones, The Animals y The Who. En 1963, a los 18 años, tocaba la armónica en el grupo Jimmy Powell and The Dimensions.
Después conoció a Long John Baldry, cantante ya entonces muy famoso. Se dice que Rod estaba cantando, borracho (el alcohol siempre ha sido una de sus grandes pasiones), en la estación de Twickenham, cuando lo vio Baldry, quien, de inmediato, le propuso unirse a él y formar un nuevo grupo. Así nacieron en la primavera de 1964, The Hoochie Coochie Men, contratados a los pocos meses por United Artists; semanas después, en junio, apareció por primera vez en un disco la voz de Stewart, a dúo con Baldry, en el tema 'Up above my head I hear music', cara B de 'You'll be mine'. Un par de meses después grabó su primer single como solista (para Decca), titulado 'Good moming little school-girl', una nueva versión de un viejo tema de Sonny Boy Williamson, acompañado por Brian Daly (guitarra), Rod Guest (piano), Bobby Graham (batería) y el futuro bajista de Led Zeppelin, John Paul Jones. Desafortunadamente, The Yardbirds (ya entonces famosos) habían publicado la misma canción. Rod no se desanimó; sólo tenía veinte años y ansias de triunfar.
A principios de 1965 entró en Steampacket, grupo protegido por Giorgio Gomelski, manager de The Yardbirds, donde compartía el papel de cantante con su amigo Baldry y con Julie Driscoll; los otros miembros del conjunto eran Brian Auger (órgano), Mick Briggs (guitarra) y Micky Waller (batería). Con esta formación Steampacket realizó una interesante mezcla de soul, jazz y blues al estilo Chicago. La experiencia duró poco. A mediados de 1966 Stewart dejó la formación para unirse al organista Peter Bardens, el guitarrista Peter Green y el cantante Beryl Marsden en Shotgun Express, con los que grabó un par de desafortunados discos, 'I could feel the whole world turn around' y 'Funny 'cos neither could I', antes de separarse a finales de ese mismo año. Pero, al mismo tiempo, el artista no descuidaba su carrera en solitario. Grabó dos canciones: 'The day will come', dirigida al mercado pop, y 'Shake', destinada a los apasionados del soul (en ella se puede advertir, en lo que respecta a su voz, la influencia de Sam Cooke).