Aunque su fortuna comenzó cuando uno de los suyos, Alfonso de Borja, se convirtió en papa con el nombre de Calixto III y el definitivo golpe de suerte les llegó cuando Rodrigo Borgia fue elegido asimismo pontífice, en 1492, como Alejandro VI, lo cierto es que los Borja —Borgia es la adaptación fonética italiana—eran una familia de antigua estirpe que aparece establecida en el Reino de Valencia desde el siglo xiii.
Remontándonos un poco más atrás en la historia, sus orígenes están ligados a la localidad de Borja, en la provincia de Zaragoza, en el Alto Aragón, y a su disputada fortaleza. Tomada en la Edad Media por los moros que habían expulsado del territorio a los cristianos, la denominación de la localidad deriva de la etimología árabe que le dieron los musulmanes, que se establecieron en el siglo viii sobre la antigua Borsao. A principios del siglo xii se inició desde Navarra la reconquista del valle del Ebro y el castillo de Borja fue recuperado en 1120, de manera pacífica, por las fuerzas de Alfonso I. El escudo de armas de los Borja mostraba en su campo superior, precisamente, el castillo con sus muchas torres.
La ascensión social de los Borja aragoneses comenzó en 1348 con el apoyo a Pedro IV el Ceremonioso en la Guerra de la Unión, revuelta encabezada por la ciudad de Valencia y seguida por varias villas y aldeas del reino, excepto Burriana y Xàtiva.
Años más tarde, cuando a mitad del siglo xiii Jaime I se lanzó a la conquista del vecino reino musulmán de Valencia, formaban parte de su ejército romana. En esta ciudad de la Corona, que poseía un buen castillo, hospitales y conventos, nueve miembros de la familia Borja recibieron tierras como recompensa a los méritos demostrados en el campo de batalla, y allí se asentaron con Esteban Borja como jefe del clan. A finales del siglo xiv, su linaje estaba tan bien considerado que Rodrigo Gil (abuelo de Alejandro VI) pudo escoger como esposa a una joven de una distinguida familia de la nobleza local. Esta primera dama de la familia, una Doms, llevaba en su escudo tres rayas doradas sobre paño azul oscuro, que Alejandro VI haría que figurasen más tarde en el escudo familiar.