In early 1948, Hines joined up again with Armstrong in the "Louis Armstrong and His All-Stars" "small-band". It was not without its strains for Hines. A year later, Armstrong became the first jazz musician to appear on the cover of "Time" magazine (on February 21, 1949). Armstrong was by then on his way to becoming an American icon, leaving Hines to feel he was being used only as a sideman in comparison to his old friend. Armstrong said of the difficulties, mainly over billing, "Hines and his ego, ego, ego ...", but after three years and to Armstrong's annoyance, Hines left the All Stars in 1951.