Together with his father, Niccolò, tyrant of Città di Castello, and his brothers, who were all soldiers of fortune, he instituted a new type of infantry armed with sword and pike to resist the German men-at-arms, and also a corps of mounted infantry armed with arquebuses. Vitellozzo took service with Florence against Pisa, and later with the French in Apulia in 1496 and with the Orsini faction against Pope Alexander VI.
In 1500 Vitellozzo and the Orsini made peace with the pope, and the latter's son Cesare Borgia, being determined to crush the petty tyrants of Romagna and consolidate papal power in that province, took the condottieri into his service. Vitellozzo distinguished himself in many engagements, but in 1501 he advanced against Florence, moved as much by a desire to avenge his brother Paolo, who while in the service of the Republic had been suspected of treachery and put to death (1499), as by Cesare's orders. While Borgia was actually negotiating with the republic, Vitelli seized Arezzo. He was forced by Borgia and the French to give up the city, to his chagrin, and he began from that moment to nurture hostile feelings towards his master and to aspire to independent rule. Vitellozzo Vitelli wanted revenge for his brother's death. Seizing Arezzo forced scare upon the Florentines and almost forced Cesare to attack Florence, but this action was in conflict with the wishes of Louis d'Orleans, king of France.
He took part with the Orsini, Oliverotto da Fermo and other captains in the conspiracy of La Magione against the Borgia, but mutual distrust and the incapacity of the leaders before Cesare's energy and the promise of French help, brought the plot to naught, and Vitelli and other condottieri, hoping to ingratiate themselves with Cesare once more, seized Senigallia in his name. There they were tricked by him and arrested while their troops were out of reach. Vitelli and Oliverotto were strangled that same night (31 December 1502).