Rozbił powstańców pod Cholet i w innych starciach. Sukcesy stały się kolejnym stopniem kariery, mianowany generałem dywizji przeszedł do Armii Północy, później Sambry i Mozy. Pod dowództwem gen. Jourdana 26 czerwca 1794 walczył w bitwie pod Fleurus, po której armia zajęła Belgię i wkroczył do Holandii. Sam Kléber wyróżnił się przy zdobyciu Maastrichtu. Pobity wróg został wyparty za Ren, Francuzi zajęli Kolonię i Bonn, a Prusy wycofały się z wojny. W styczniu 1795 roku Kléber kolejny raz w życiu stanął pod Moguncją. Tym razem dowodził oblężeniem. Wkrótce Austria ruszała z nową ofensywą, która przyniosła im kolejne sukcesy. W 1796 roku arcyksiążę Karol bije Jourdana pod Ambergiem i Würzburgiem. Mimo pewnych sukcesów Klébera 19 września pod Altenkirchen, armie francuskie wycofały się za Ren.
Po wygraniu kampanii włoskiej Napoleon zaczął przygotowania do wyprawy egipskiej dzięki czemu Kléber, zwróciwszy uwagę Napoleona, stał się jednym z ważniejszych oficerów Armii Egiptu. Ostatecznie flota ruszyła 19 maja 1798 roku. Kléber znajdował się na pokładzie „Franklina”, z którego zsiadł 30 czerwca, by stanowić prawe skrzydło lądującej armii. W czasie marszu na Aleksandrię oddziały Klébera szły w centrum w towarzystwie Bonapartego i jego sztabu.