Una noche de 1941 un saxofonista no se presentó a un concierto con la banda y Houston tomó su lugar.

Después de la Segunda Guerra Mundial, Houston volvió a Texas, grabando con el pianista Amos Milburn y el cantante Big Joe Turner.

[2]​ Al principio tocó el saxo alto, pero lo cambió por el tenor a raíz de saxofonistas como Big Jay McNeely y Paul Williams.

De forma eventual, Houston creó su propia banda The Rockets, y se trasladaron a Los Ángeles en 1952.

Hizo giras y grabó con su banda the Defrosterz, inicialmente compuesta por Mark St.