Gonzalo Fernández de Córdoba era un noble andaluz de la familia Aguilar, proveniente de Galicia y había descendido hacia el sur según progresaba la Reconquista a los musulmanes de Al-Ándalus.
Gonzalo había nacido en Montilla (Córdoba) en 1453, poco se sabe de su infancia. Su padre falleció cuando Gonzalo tenía dos años y así su hermano mayor Alfonso de Córdoba se convirtió en jefe de la casa de Aguilar. Dentro de su familia, Gonzalo estaba destinado a ser un segundón; nadie pensaba que se convertiría en un gran militar de las Españas.
Intentando darle un futuro, su hermano Alfonso le hizo paje del Arzobispo Carrillo, personaje muy cercano a Isabel la Católica. En la corte de la Princesa Isabel el joven Gonzalo, que tenía quince años, destacó en los juegos y con las armas. Al ser paje del Arzobispo Carrillo, Gonzalo hubo de estar presente en el pacto de Toros de Guisando de 1468 en el que el Rey Enrique IV reconoció a Isabel la Católica como heredera en el trono de Castilla. También debió de estar presente en la boda de los príncipes Isabel de Castilla y Fernando de Aragón llevada a cabo en Valladolid en 1469.
En 1473, a sus 20 años, Gonzalo volvió a Córdoba y contrajo matrimonio. Poco después fue hecho prisionero por el Conde de Cabra, cuya casa era la tradicional enemiga de la casa de Aguilar en el círculo de los conflictos nobiliarios que por aquel entonces sacudían al reino de Castilla. Dos años más tarde, la ya reina Isabel la Católica gestionó su libertad y viajó a Córdoba en 1478 para reconciliar a las dos familias, objetivo que consiguió.