Even though he has turned in one stunning performance after another on albums by Paul Motian’s Electric Bebop Band, Charlie Haden’s Liberation Music Orchestra, Guillermo Klein’s Los Gauchos and various lesser-known, though equally interesting ensembles, Chris Cheek is still a lurker.

Your only good chance of seeing this reedman live is in New York or on the other side of the pond, where he makes frequent tours. The problem has nothing to do with Cheek’s playing. It’s the game: labels, distributors, publicists, writiers, editors. Nevertheless, Blues Cruise did get to me by some freakish fluke, and I’ve gotten to savor its pleasing variety of textures and styles.

The erstwhile Brad Mehldau Trio is the backing band on Blues Cruise. Cheek couldn’t have asked for a more empathetic and sensitive rhythm team for this program, which ranges from the calypso-tinged “Flamingo” to the soft Rhodes-laden bossa-tango “Coo” and the folk rock-informed “John Denver,” which actually sounds like a convincing jazz version of what would otherwise be a rock song with electric guitars and bass.

The title of this release would seem to imply that the tunes center around the blues, but they don’t, really. Some have a bluesy flavor. But it seems to be more about the journey. The soprano ballads have a searching quality, while the tenor romps are more declaratory.

The saxophonist’s rich tone is the most notable constant throughout the record. It has a richness and flavor that's akin to a fine wine or cigar. The vivacity and frolicking quality of Cheek’s breathy tenor owe much to the influence of Sonny Rollins, while his rhythmic flair draws equally from Eddie Harris. Comparisons to Chris Potter and Donny McCaslin also come to mind, but without all the shrieking and pyrotechnics.

This record is a testament to the fact that no matter how far any player may be from the media limelight—and consequently the public consciousness—a great soloist coupled with a terrific backing band can make for some of the freshest music you’ve ever heard.