W 1424 r. służył pod rozkazami Muzia Attendola Sforzy, przy którym uczył się sztuki i taktyki wojennej. Następnie walczył pod dowództwem słynnego Francesco Bussone, zwanego Carmagnolą. Pomiędzy kolejnymi wyprawami pojął za żonę Tisbe Martinengo, a w 1431 r. kupił pałac przy via Tassis w Bergamo. Po zgładzeniu Carmagnoli w Wenecji (1432 r.), Colleoni przeszedł na bezpośrednią służbę Republiki Weneckiej, rozpoczynając tym samym główną część własnej kariery. Pomimo iż nominalnym naczelnym dowódcą był Gianfrancesco Gonzaga, Colleoni stał się faktycznym przywódcą wojska. Odbił liczne miasta i gminy z rąk Mediolanu dla Wenecji. Gdy Gonzaga przeszedł na stronę wroga, Colleoni dalej służył Wenecji pod Erazmusem z Narni (znanym jako Gattamelata) i Franciszkiem Sforzą, wygrywając bitwy pod Brescią, Weroną i nad jeziorem Garda.
W trakcie wyprawy w 1439 r. Colleoni przeciągnął z Zatoki Weneckiej na jezioro Garda flotę złożoną z 3 galeonów, 3 galer, 1 wielkiej barki weneckiej i 25 mniejszych jednostek. Większe statki wciągano w górę doliny Adygi na drewnianych walcach przy użyciu zaprzęgów złożonych w sumie z 2000 wołów. Dwa tysiące robotników równało drogi, budowało przejścia przez wąwozy, wzmacniało mosty.