Hines was born in Pittsburgh, Pennsylvania. His father was a brass band cornetist, and his mother a church organist. Hines at first intended to follow his father's example and play cornet, but then developed a greater attraction to the piano.
At the start of the 1920s he was playing professionally around Pittsburgh. About 1923 he moved to Chicago, Illinois, then the world's jazz capital. He played with the bands of Carroll Dikerson and Erskine Tate, then in 1927 began playing with Louis Armstrong. Armstrong was very impressed with Hines' playing style, quite creative and avante guarde for the era. That year Armstrong revamped his Okeh Records recording band, "Louis Armstrong's Hot Five", and replaced his wife Lil Hardin Armstrong with Hines.
Armstrong and Hines recorded what are regarded as some of the most important jazz records of the late 1920s.
In the 1930s Hines began leading his own band, touring with bases varying from Chicago to New York and back, and making a series of radio broadcasts. He toured Europe later in the decade, was based in Switzerland for a time, then returned to the USA in 1940. He led a big band until 1947, taking time out to front the Duke Ellington orchestra in 1944 while Duke was ill.
At the start of 1949 Hines rejoined Armstrong in the later's "All Stars", where Hines stayed through 1951. He then led a small band around the States and Europe. He settled in Oakland, California at the start of the 1960s. Hines continued touring, adding Asia and Australia to his list of destinations, through the early 1980s, playing his last jobs a few days before his death in Oakland.