1488년 그는 첫 아내 (마르게리타 콜레오니, Margherita Colleoni)가 사망한 후, 베아트리체 다발로스와 재혼했다. 같은 해 6월 그는 나폴리 왕국과 그곳의 통치자 페르디난도 1세 디 나폴리에게서 복무하기 위해 이탈리아 남부로 이동했다.
같은 해 밀라노 공작인 잔 갈레아초 스포르차가 알폰소 공작의 딸이자 페르디난도의 손녀인 이사벨라 다라고나와 혼인했다. 1493년에 그 젊은 공작(잔 갈레아초 스포르차)이 장인에게 그의 숙부인 섭정 루도비코 일 모로에게서 공작 자리를 되찾는 것을 지원해줄 것을 요청했다. 그러자 루도비코는 샤를 8세에게 나폴리를 공격해달라고 요청했다. 1494년 샤를 8세는 이탈리아 원정을 실시했다. 샤를 8세은 이탈리아에서 모든 저항을 이겨내고 곧 나폴리가 강화 조약을 맺게끔 했다. 그 강화 조약은 당시 나폴리군의 최고 사령관이던 트리불치오가 협상을 했다. 트리불치오의 능력에 감탄한 샤를은 그를 고용하기로 결정했고, 페르디난도의 허가를 받아 연간 10,000 두캇의 봉급을 주기로 하였다.
트리불치오는 샤를의 군대와 함께 프랑스로 향했다. 프랑스군이 퇴각하던 도중 베네치아 동맹의 공격을 받은 포르노보 전투 (1495년)에서 그는 프랑스군과 함께 싸웠다. 1495년 6월 15일에 그는 아스티의 총독으로 임명됐고 귀족 작위와 함께 프랑스내 영지를 수여받았다. 1498년 샤를이 사망한 후, 그의 후계자 루이 12세는 루도비코로부터 밀라노 공국을 점령하기 위해 트리불치오가 이끄는 대군을 소집했다. 트리불치오는 몇몇 요새화된 도시들을 점령하고 루도비코가 밀라노를 포기하게 끔 하였다. 1499년 10월 6일 그는 루이 12세에게 밀라노의 열쇠를 선물하였다. 루이는 그를 밀라노 총독으로 임명했고; 당시 그는 이미 9월 29일에 프랑스 육군원수로 임명됐었다.