Aparece por vez primera con el grado de capitán en la toma de Antequera (1410), aunque su fama aumentó en la batalla de Loja al conseguir la plaza casi de forma incruenta. Participó en la conquista del reino de Granada, destacando su intervención en las negociaciones para la rendición. A poco, el papa Alejandro Vl solicita sus servicios para la recuperación de Ostia, en Italia, puerto que se encontraba dominado por el corsario Menalgo Guerri, impidiendo así todo suministro de abastecimiento a Roma. El Gran Capitán acaba con la pesadilla y por esta razón es recibido en la Ciudad Eterna como lo merece un héroe. De regreso a España sofoca las revueltas de Las Alpujarras. Para entonces, Federico III le había confiado los ducados de Terranova y Santángelo con todas sus tierras y fortalezas. Sin embargo, pronto sería requerido de nuevo en Italia. Ante el ataque turco en Lombardía y la amenaza sobre Venecia, Fernando el Católico envía un ejército a cuyo frente va Gonzalo, quien forzó la huida de la escuadra turca. Prosiguen sus campañas italianas. En 1503 conquista el reino de Nápoles (batallas de Ceriñola y Garellano), pero su innata modestia le impide aceptar los homenajes mundanos que se le querían tributar. A partir de este momento atravesará una de las etapas más tristes y grises de su vida, debido a circunstancias ajenas a su profesión. La muerte de la reina Isabel en 1504, soberana que le dispensaba con su protección y por quien sentía sincero respeto, causa tan profunda impresión en su ánimo que enferma en Italia. Solicita el regreso a España, petición que reiteradamente se le deniega, en parte por el recelo que inexplicablemente despierta en el rey Fernando. El Gran Capitán cae en el desengaño. Hasta 1505 el rey no decide su relevo, y ambos viajan juntos desde Italia a España. Se retira a su casa de Loja, ciudad que le pertenecía por concesión real, sumido en un profundo abatimiento. Pero aún debía soportar otra prueba más. En 1508 recibe la noticia de que el monarca proyecta la demolición del castillo de Montilla, su ciudad natal. Vanas fueron sus súplicas por hacerle cambiar de opinión. Este nuevo gesto de humillación que sufrió supuso la ruptura definitiva con el rey, a quien siempre había profesado una sincera lealtad. Enfermó gravemente en Loja, donde murió. Sus restos mortales fueron trasladados con posterioridad a la iglesia de San Jerónimo de Granada.