Fue gracias a estos dos personajes que Tommy consiguio su primer contrato discografico con una compañia multinacional de gran prestigio, Decca, cuya filial inglesa contrato en 1956 al joven guitarrista. Asi fue como Tommy Steele grabo su single de debut. Merece la pena señalar que Decca lo contrato despues de que fuera rechazado por EMI a causa de la negativa de George Martin, el futuro productor y arreglista de los Beatles. Mucho mas interesado por el talento de Steele estaba, en cambio, el responsable de Decca, Hugh Mendl, quien andaba buscando un cantante de rock’n’roll desde hacia tiempo. Finalmente lo encontro el dia en que Kennedy y Parnes, quienes habian asumido todos los gastos del gran lanzamiento de Tommy, le presentaron a su pupilo proponiendole que le hiciera una prueba en el estudio. Era la gran oportunidad para el cantante ingles, y este no la desaprovecho. El primer single de Tommy tenia en una cara 'Rock with the caveman', una cancion que el mismo habia escrito con la colaboracion de dos profesionales (Mike Pratt y Lionel Bart), y en la otra una cancion copiada de un exito americano, 'Rock around the town'. Para acompañar a Tommy se formo una banda constituida por musicos de jazz y liderada por el prestigioso saxofonista Ronnie Scott, aunque en la portada del disco simplemente aparecia el nombre de su conjunto, The Steelmen.
Steele presento su disco de debut en television, interpretando en directo aquellos dos temas en el importante show Off the record, un programa dirigido por Jack Payne que era muy seguido por el publico juvenil. Tras Bill Haley y Elvis Presley, Tommy Steele fue el tercer artista en difundir el rock’n’roll en el Reino Unido, siendo el primer ingles que se dedico a este genero musical. Bien fue la cosa, ya que despues de su aparicion televisiva, en noviembre, 'Rock with the caveman' ya estaba en el numero trece de las listas britanicas. Steele y los Steelmen ya tenian el prestigio suficiente como para pasar de los pubs del Soho a locales de mayor importancia, como el Empire Theatre, don de actuaron en noviembre de aquel decisivo 1956. En diciembre el grupo, que incluia al guitarrista Roy Plummer y al saxofonista Alan Stewart, y su lider saboreaban la histeria de los fans, lo que recordaba a las acogidas que Elvis Presley tenia en America. A pe sar de este exito, el segundo sencillo, 'Elevator rock', no consiguio abrirse un hueco en las listas. Hecho remediado en el mismo mes de diciembre por el tercer single, que presentaba su 'Singing the blues', version de un tema llevado al exito en America por G. Mitchell y que se catapulto al vertice de las listas inglesas, alcanzando su numero uno en el acto.
Aunque habia algo que no marchaba bien en la carrera de Tommy Steele. Con seguridad era el primer rocker ingles y europeo, pero en su pais el ambiente musical era demasiado tradicionalista como para concederle el espacio que se le dejo, de mala gana, a Elvis Presley, y el mismo, por otro lado, no conseguia sentirse como un verdadero rocker. De modo que sus siguientes discos, publicados entre 1957 y 1958, se inclinaron cada vez mas hacia un estilo mas melodico y tradicional. Esto sucedio con canciones como 'Butterfingers', 'Shiralee', 'Water & water', 'Nairobi' y 'The only man on the island'. Entre tanto, en febrero de 1957 interpreto un papel en la pelicula 'Kill me tomorrow', y ademas anuncio su coparticipacion en un film semiautobiografico, 'The Tommy Steele Story'. Luego grabo otro exito de Guy Mitchell, 'Knee deep in the blues', pero mientras la version del cantante original llego al cuarto puesto de las listas la version de Steele apenas alcanzo el numero quince. Otros de sus discos tuvieron mejor fortuna y en octubre Tommy volvio a los estudios para rodar una nueva pelicula, 'The duke wore jeans'.