Gutierre Gómez de Toledo fue hijo de Tel (Tello) Fernández de Toledo y de Mencía Fernández de Toledo, así reza en el testamento del prelado hecho en Segovia el 13 de septiembre de 1387. El historiador M. Risco se equivoca al hacerle hijo de Fernán Vicente, alcalde mayor de Toledo. Era el segundo de doce hermanos, seis de los cuales habrían nacido de un segundo matrimonio de su padre, don Tello, con Teresa Alfonso de Aza. Recibió el santo bautismo en la parroquia de San Justo, a cuyo distrito pertenecía la casa de sus padres. Su nobilísima familia fue mozárabe —antiguos cristianos que se hallaban en la ciudad de Toledo en el momento de su conquista y que habían permanecido en la fe cristiana durante la invasión musulmana—.

Su tío, Gutierre Fernández de Toledo, señor de Anamella, repostero, guarda mayor y jefe de las tropas del rey don Pedro, quien había ocupado otros cargos con Alfonso XI, fue mandado ajusticiar en Alfaro por el Rey Cruel en 1360. Esteban, su hermano mayor, escogió la carrera clerical y sólo llegó a obtener varias prebendas canonicales: maestrescuela de Palencia y canónigo-deán de Oviedo, a la sombra de su tío y su hermano Gutierre. Otros dos miembros de la familia se llamaron de igual modo, uno fue prior de la Orden de San Juan de Jerusalén durante la primera mitad de la década de 1360, y otro, el ya mencionado Gutierre, que fue obispo de Palencia desde 1357 y cardenal bajo la obediencia de Aviñón. También fue pariente suyo Blas Fernández de Toledo, obispo de Palencia desde 1343, quien, junto a Gutierre Fernández de Toledo, apoyaría decididamente el gobierno de Juan Alfonso de Alburquerque y de la reina María durante los primeros años del reinado de Pedro I. Algunos de estos familiares del personaje aparecen en la Crónica de Pero López de Ayala como privados del Rey. [...]