Era hija del doctor Juan Alonso de Ulloa y Monterroso, señor de Villabarca, consejero real de Juan II de Castilla, y de su esposa Beatriz Rodríguez de Fonseca,^[1]​ hija del señor portugués de Olivenza, Barqueiros, Sousel y Panóias, Pedro Rodríguez de Fonseca, que fue guarda mayor de Juan I de Castilla, y de su esposa Inés Díaz Botelho. Hermana de Alonso I de Fonseca, señor de las villas de Coca y de Alaejos y arzobispo de Sevilla y prima de Pedro Yáñez de Ulloa, I señor de la Mota.^[2]​^[3]​

Se casó en 1424 con Diego González de Acevedo, contador del Reino de Castilla y señor del mayorazgo de Taxado, etc, que acompañó a Enrique IV y a Juan II en sus luchas contra los moros,^[4]​ hijo de João Gonçalves de Azevedo luego Juan González de Acevedo (?-Salamanca, 24 de marzo de 1424, sep. Iglesia de San Francisco de Salamanca), Doctor, leyente en la Universidad de Salamanca, y de su esposa Aldonza Díaz Maldonado, con el que tuvo cinco hijos y hijas:^[2]​^[3]​

• el arzobispo compostelano Alonso de Fonseca y Acevedo o Alonso II de Fonseca
• Luis de Acevedo y Fonseca, casado con Teresa das Mariñas de Haro, hija de Gómez Pérez das Mariñas, señor de la casa das Mariñas, y de su esposa Teresa de Haro y Acuña, cuñada del I conde de Villalba y tía materna del I conde de Andrade y de Gómez Pérez das Mariñas
• Aldonza de Acevedo y Fonseca, primera esposa de su primo Lope Sánchez de Ulloa y Moscoso, I conde de Altamira
• Juana de Acevedo y Fonseca, casada con Rodrigo de Mendoza y Córdoba, señor de Santa Cecilia y de la Casa de Almanza, con descendencia
• María de Acevedo y Fonseca, casada con Pedro de Vega

Su padre era el hijo unigénito y póstumo de Juan González de Acevedo, fallecido en Salamanca el 24 de marzo de 1424, Doctor,^[2]​ Leyente en la Universidad de Salamanca, sepultado en la Iglesia de San Francisco de Salamanca con su esposa Aldonza Díaz Maldonado, nacida alrededor de 1406, con la cual casaría en 1424. Nieto paterno de Martín González de Acevedo que pasó a Castilla y del que descienden los condes de Monterrey por varonía, los condes de Fuentes de Valdepero y los de Ayala con los marqueses de Monterroso y no usan las armas de los de Portugal. Hijo segundo de Gonzalo Vázquez de Acevedo (I señor de la Lourinhã, de Figueiró dos Vinhos y de Pedrógão Grande, alcaide mayor de Santarém y de Torres Novas y I mariscal del Reino de Portugal) y de su esposa Inés Alfonso. ^[2]​

Según García-Fernández (2013),^[5]​ Catalina de Fonseca, siendo ya viuda de Acevedo, trató de salvaguardar los intereses de su hijo, Alonso II de Fonseca, el cual había sido hecho prisionero por Bernal Yáñez de Moscoso en el contexto de la revuelta de los compostelanos contra su señor, para lo cual dispuso que se tomasen, ante notario, un conjunto de alhajas y monedas viejas del tesoro de la Catedral por valor de dos mil cuatrocientos reales, para pagar el rescate exigido para la liberación del Arzobispo. Terminó por hacer presos a los beneficiados del Cabildo y llegó a convertirse en cabecilla de la resistencia en la Catedral de Santiago, en la que permaneció encerrada junto con su otro hijo, Luis de Acevedo, y un reducido número de clérigos y hombres de armas, ante el asedio que sufrieron por parte de los rebeldes.

• Carrasco y Cifuentes, Lorena: La venganza: raíz de la conflictividad de la nobleza gallega bajomedieval. Los enfrentamientos entre los Moscoso y el arzobispo Fonseca (1464-1473). Revista De Medio Aevo 7 (2015 / 1) ISSN-e 2255-5889