W 1969 założył The Rhythm Combination and Brass (RC&B), orkiestrę o oryginalnym instrumentarium z wyeksponowaną sekcję „blachy” i tylko jednym saksofonem. Grali w niej muzycy z wielu krajów Europy i Stanów Zjednoczonych. RC&B często koncertowała w Niemczech i za granicą (również w Polsce m.in. na festiwalach „Jazz Jamboree” w 1975 i 1987), występowała w radiu i telewizji, oraz dokonywała licznych nagrań. Szybko stała się czołowym big-bandem Europy. Jej stylistyka ewoluowała od jazz-rocka, przez jazz z elementami latynoskimi, nurt straight-ahead aż do swingowej klasyki big–bandowej. Dziełem Herbolzheimera były aranżacje niemal całego repertuaru RC&B. W latach 70. jego zespół (w większości złożony z muzyków RC&B) z powodzeniem występował w telewizji publicznej ZDF i na tournées z programem „gali jazzowej” z gościnnym udziałem takich gwiazd jazzu, jak Ella Fitzgerald, Benny Goodman, Dizzy Gillespie, Clark Terry, Gerry Mulligan, Stan Getz, Nat Adderley, Esther Phillips, Gary Burton, Toots Thielemans i Albert Mangelsdorff. Często pojawiał się także na międzynarodowych festiwalach jazzowych, m.in. we francuskim Antibes.