Gilmore grew up in Chicago and played clarinet from the age of 14.  He took up the tenor saxophone while serving in the United States Air Force from 1948-1952, then pursued a musical career, playing briefly with pianist Earl Hines before encountering Sun Ra in 1953.
For the next four decades, Gilmore recorded and performed almost exclusively with Sun Ra. This was puzzling to some, who noted Gilmore's talent, and thought he could be a major star like John Coltrane or Sonny Rollins. Coltrane, in fact, was impressed with Gilmore's playing, and took informal lessons from him in the late 1950's. Coltrane's epochal, proto-free jazz Chasin' the Trane was inspired partly by Gilmore's sound.