Besides being one of the first jazz musicians to convert to Islam and change his name (1947), Sahib Shihab was also one of the earliest boppers to use the flute. But he was also a fluent soloist on the alto, as well as the baritone sax, the latter being the instrument with which he became most frequently associated. Shihab first worked professionally with the Luther Henderson band at the age of 13 while still studying with Elmer Snowden. At 16, he attended the Boston Conservatory (1941-1942) and later worked as the lead alto in the 1944-1945 Fletcher Henderson band, billed as Eddie Gregory.
After his religious conversion, he fell in with the early bop movement, recording several now-famous sides on alto with Thelonious Monk for Blue Note in 1947 and 1951, and playing with Art Blakey in 1949-1950 and the Tadd Dameron band in 1949. Following some empty patches where he had to work odd jobs for a living, Shihab played with Dizzy Gillespie in 1951-1952, Illinois Jacquet in 1952-1955, and the Oscar Pettiford big band in 1957. After arriving in Europe with Quincy Jones' big band in 1959-1960, he remained there until 1986 (mostly in Copenhagen), except for a long Los Angeles interlude (1973-1976).