Nel 1502 Leonardo venne assoldato da Cesare Borgia in veste di architetto e ingegnere militare. I due avevano già avuto modo di conoscersi a Milano nel 1499. Il figlio di papa Alessandro VI, detto "duca del Valentino", fu uno dei tiranni più feroci del momento ed occupò Leonardo, che era giunto a Cesena, in varie mansioni legate alle continue campagne militari, come rilevare e aggiornare le fortificazioni delle città di Romagna conquistate. Per lui mise a punto un nuovo tipo di polvere da sparo, formata da una miscela di zolfo, carbone e salnitro, studiò macchine volanti e strumenti per la guerra sottomarina. In agosto soggiornò a Pavia, da dove partì per ispezionare le fortezze lombarde del Borgia; disegnò inoltre mappe dettagliate per facilitare le mosse strategico-militari dell'esercito.
Al seguito del Valentino assistette a una delle più sanguinose e crudeli campagne dell'epoca, l'attacco a tradimento contro Urbino. Proprio a Urbino Leonardo strinse rapporti d'amicizia con Niccolò Machiavelli, probabilmente già conosciuto a Firenze.