Po wybuchu powstania, w styczniu 1863, zgłosił swoje usługi polskim władzom powstańczym i wyruszył z grupą wychowanków do obozu powstańczego Apolinarego Kurowskiego w Ojcowie. Tam, opierając się na wzorach francuskich, Rochebrune stworzył oddział nazwany żuawami śmierci. Pierwszy raz weszli do walki 17 lutego w bitwie pod Miechowem, w której, mimo utraty elementu zaskoczenia, Rochebrune osobiście poprowadził atak na bagnety na pozycje rosyjskie na cmentarzu, wyrywając karabiny z rąk Rosjan. Po poniesieniu dużych strat, Rochebrune, który zaczął swoje nazwisko pisać wówczas jako „de Rochebrune”, odtworzył swoją formację w Krakowie. Pod twardą ręką Rochebrune’a, egzekwującego dyscyplinę, żuawi stali się jedną z doborowych formacji powstania. Następnie szkolił także oddziały polskich kosynierów. Według części źródeł uczestniczył w bitwie pod Małogoszczem, lecz brak relacji o udziale żuawów w tej bitwie. Żuawi pod jego osobistym dowództwem walczyli następnie w marcu 1863 w bitwach pod Chrobrzem i Grochowiskami. Pod Grochowiskami 18 marca Rochebrune faktycznie dowodził całością sił powstańczych biorących udział w bitwie, opanowując chaos, gdy sztab Langiewicza utracił kontrolę nad oddziałami, a następnie na czele kosynierów poprowadził atak na rosyjską piechotę.