El Cardenal Mendoza dedicó gran parte de sus riquezas al mecenazgo artístico y benéfico allí donde tuvo algún tipo de dignidad o posesión. Uno de ellos fue el Colegio Mayor de Santa Cruz, devoción personal porque había nacido un 3 de mayo, fecha de la invención de la Cruz de Cristo por Santa Elena.

Una bula de Sixto IV de 29 de mayo de 1479 aprobaba la fundación del centro. Otra de 16 de enero de 1482 confirmaba y ratificaba la anterior. El 21 de noviembre de 1483, Mendoza expedía en Vitoria el documento de fundación. El 17 de julio de 1484 el mismo Papa publicaba una Bula de confirmación de su concordia con la Universidad de Valladolid. Fue entonces cuando publicó oficialmente en Guadalajara las Constituciones redactadas en Vitoria.

El Colegio se fundó con veinte colegiales en 1484, quienes se alojaron en unas casas en la cercana calle de la Merced hasta que se construyera el nuevo edificio. En 1486 se comenzó la construción del nuevo Colegio, a lo que destinó cuantiosas sumas administradas por su mayordomo, Alfonso de Villanueva. La supervisión de la nueva construcción fue llevada a cabo primero por el bachiller Juan de Foncea, hasta 1488, y luego por el teólogo Toribio de Bedoya.

No se sabe quien fue el autor del primer proyecto del edificio, pues no parece fundada la atribución a Enrique Egas. Se sabe que lo elevaban cuatro maestros de cantería, dos de ellos llamados Juan de la Riva y Pedro Polido. La obra se inició en estilo gótico final, hasta 1488 cuando el mecenas vió lo construido y no lo encontró de suagrado, momento en el que debió entrar a dirigir la construcción Lorenzo Vázquez de Segovia, al que el Cardenal cita como "maestro de nuestras obras".

De formación italiana, probablemente en torno a Bolonia, Ferrara, o incluso la Toscana, Lorenzo Vázquez sería el que introduce las notas renacentistas en el edificio, el primero en España en este estilo. Pudo empezar a trabajar en el Colegio a partir de 1489 y lo terminaría en lo esencial en 1491, como indica la inscripción del zaguán. Al año siguiente estaría habitable, procediéndose al traslado de los colegiales. Ese año se encargó de pintar la librería Pedro Gumiel. En su testamento de 1494, el Gran Cardenal destinó 200.000 maravedíes para la ejecución de un retablo para la capilla.