El rey Fernando el Católico le recompensó dándole la investidura del condado de Alveto u Oliveto, situado en la Italia meridional. Al finalizar la segunda campaña de Italia, Pedro Navarro regresó a España, donde el rey Fernando le ordenó marchar contra el duque de Nájera, que se había revelado (1507). El duque no se atrevió a combatir contra un enemigo de tanto crédito y entró rápidamente en negociaciones para concertar la paz.

A continuación, en 1508 el rey Fernando el Católico le ordenó perseguir con una escuadra española los piratas berberiscos que habían asolado las costas sevillanas. La expedición partió de Málaga, y Pedro Navarro se aplicó a ello con eficacia, limpiando de piratas tanto las cosas españolas como las africanas. El 23 de junio conquistó el peñón de Vélez de la Gomera. Posteriormente auxilió desde el mar a la guarnición portuguesa de Arcila.

Puesto al frente del ejército que el cardenal Cisneros financió con las rentas de su cargo de arzobispo de Toledo, efectuó la conquista de Orán en 1509. Al año siguiente protagonizó la primera campaña de Túnez, en la que conquistó Bujía, con lo que Argel, Túnez y Tremecen se sometieron a la autoridad de España. La derrota y muerte de García de Toledo en la isla de Yerba y la falta de medios le obligaron a interrumpir sus conquistas en el norte de África. Dejó a don Diego de Vera al mando de Trípoli y regresó a España.

En España pasó poco tiempo ocioso, pues regresó a Italia en 1512 para ponerse a las órdenes del virrey de Nápoles don Ramón de Cardona y participar en la tercera campaña de Italia (1511-1513), librada por España, Venecia y el Papa, que formaban una Santa Liga, para expulsar a los franceses de Italia. En esta campaña Pedro Navarro se distinguió tomando la inexpugnable ciudad de Bastia en tan solo cinco días. Pero en el sitio de Bolonia (1512) las minas de Pedro Navarro fracasaron debido a la humedad y al escaso tiempo disponible para preparar sus minas. Ramón de Cardona ordenó levantar el sitio y los franceses continuaron dueños de Bolonia.

En abril de 1512 se libró la batalla de Rávena, en la que Pedro Navarro estaba al mando de la infantería española, que resistió en perfecto orden los ataques de alemanes y franceses enemigos y la retirada de la caballería aliada e infantería italiana. En la retirada final Pedro Navarro cayó herido y prisionero de los franceses. El caballero de Labrit, su captor, le condujo a Francia y le mantuvo en cautiverio tres años mientras pedía un rescate de 20.000 escudos. Don Fernando el Católico no quiso pagar el rescate de su liberación, por lo que el rey Francisco I de Francia pagó su rescate y le ofreció entrar a su servicio como general de sus ejércitos. Pedro Navarro escribió al rey Fernando el Católico para separarse de su servicio, y el rey le contestó que "podía hacerlo, pues era libre". Pedro Navarro devolvió al rey Católico el título de conde de Oliveto y la patente de general español.

Con su infantería organizada a la española, el rey Francisco I inició la cuarta campaña de Italia (1515). Al mando de la infantería francesa, en la que se incluían unos 6.000 vascos y gascones que acudieron a Francisco I espontáneamente, Pedro Navarro invadió el Milanesado en 1515 y se apoderó de las plazas de Novara, Vigenaro y Pavía. Participó en la victoria francesa de la batalla de Marignano, donde impuso una disciplina de fuego a los arcabuceros franceses que desordenó por completo a los compactos escuadrones de infantería suiza al servicio del virrey de Nápoles; se le considera el inventor del fuego a la voz por filas, utilizada por primera vez en esta batalla. Terminó su brillante campaña entrando en Milán al frente de sus tropas.

Con ocasión de la quinta campaña de Italia (1521-1522) volvió a este país con el encargo de llevar socorros al general Lautrec. Con este motivo se encontraba encuadrado en el ejército francés que fue derrotado en la batalla de Bicoca (1522) y en la que Pedro Navarro se distinguió de manera notable. Despues de la derrota, Navarro quiso llevar refuerzos a Génova, pero su llegada coincidió con la toma de la ciudad por las tropas imperiales, por lo que Navarro fue hecho prisionero por los españoles, que lo encerraron en Castelnovo durante tres años. Al firmarse el Tratado de Madrid de 1526, tras la derrota francesa de Pavía, fue puesto en libertad.

Pedro Navarro reunió tropas en Francia y con ellas marchó con el general Lautrec de nuevo a Italia. Este murió de peste en el sitio de Nápoles, y Navarro se puso a las órdenes del marqués de Saluzzo. Cuando los franceses levantaron el bloqueo de Nápoles, tuvieron que emprender una desatrosa retirada hacia Aversa, y en ella Navarro resultó de nuevo hecho prisionero por lo españoles. Fué conducido otra vez a Nápoles y encerrado por segunda vez en el castillo de Castelnovo.

Carlos I decretó su muerte por degollación, pero el virrey de Nápoles, el príncipe de Orange, quiso evitarle la vergüenza de este suplicio, por lo que "fue ahogado entre dos almohadas o estrangulado con cuerda por mano del verdugo ... estaba tan viejo y achacosa que no podía estarlo más ... Pero el emperador fue censudado, pues debía haberle impuesto una prisión perpetua, en la que hubiese podido escribir y dejar algunas interesantes memorias de su arte y ciencia ... así he oido que pensaba obrar, y aún que comenzó a hacerlo." (Brantome, en su "Vidas de los grandes capitanes".)

Pedro Navarro murió en 1528 a los 68 años en el castillo que él había conquistado 25 años antes. Al día siguiente de su muerte los españoles escribieron el siguiente epitafio:

"Ilustre capitán español muerto al servicio de los franceses."

El duque de Gesa, sobrino de El Gran Capitán, construyó un sepulcro para Pedro Navarro junto al del general Lautrec en la iglesia de Santa María la Nueva.