He has worked with Bob Brookmeyer, Fred Hersch, Tony Malaby, the Vanguard Jazz Orchestra, Kenny Wheeler, Pablo Ziegler, and Meredith Monk.

The Cloud of Unknowing, commissioned by the Bamberg Choir in Germany was released in 2001 on the Edel Classics label with works by J. S. Bach, Igor Stravinsky, and Paul Hindemith.

Hollenbeck's chamber piece, Demütig Bitten, was commissioned by the Windsbacher Knabenchor (Germany) and released in 2004 on the Rondeau label with works by Giovanni Gabrieli, Josquin des Prez, and Johann Sebastian Bach.

Hollenbeck's recording career as a leader began in the winter of 2001 with: no images, which Gary Giddins included in his Village Voice 2001 top ten list, Quartet Lucy, and the Claudia Quintet.

[4] His second large ensemble recording, Joys and Desires, featuring Jazz Big Band Graz and Theo Bleckmann, was released by Intuition in 2006 to critical acclaim.