Coleman was born in Fort Worth, Texas. He began playing R&B and bebop music, at first on the tenor saxophone. He wanted to leave his home town so he got a job in 1949 with a traveling show. Then he played with touring R&B shows. In Baton Rouge, he was attacked and his saxophone was destroyed. After that he changed to the alto saxophone, and that is still the instrument he usually plays. He joined a band and traveled with them to Los Angeles, in California. He worked at different jobs while still trying to be successful as a musician.