C'est en 1869 qu'est fondée la première paroisse catholique de la ville, alors placée sous la juridiction du diocèse de Galveston. Il faut attendre encore trois ans pour que la communauté se dote d'une modeste église en pierre, consacrée sous le nom d'église du Sacré-Cœur.
En 1890, le pape Léon XIII créé le diocèse de Dallas, entraînant de fait la transformation de l'église en cathédrale. Thomas Brennan en devient le premier évêque. Durant son bref épiscopat (1890-1892) il organise la communauté des fidèles. C'est néanmoins son successeur Edward Joseph Dunne (1893-1910) qui ordonne et supervise la construction d'un nouveau sanctuaire. Il confie le soin de dessiner les plans de la future cathédrale à l'architecte texan Nicholas J. Clayton, qui imagine un édifice néo-gothique, un parti architectural en vogue durant une grande partie du XIX siècle.
La première pierre est posée le 17 juin 1898 . Un peu plus de quatre ans plus tard, le gros-œuvre est achevé et la cathédrale, placée sous l'invocation du Sacré-Cœur, est consacrée au cours d'une cérémonie solennelle le 26 octobre 1902.
Le développement de l'agglomération (formant une conurbation connue sous le nom de Dallas-Fort Worth Metroplex) au cours de la seconde moitié du XX siècle et l'arrivée massive d'immigrants en provenance du Mexique voisin (généralement catholiques) permet la croissance rapide de la communauté des fidèles et l'établissement de nouvelles paroisses.
Dans les années 1960, la paroisse du Sacré-Cœur entame un rapprochement avec celle, voisine, de Notre-Dame de Guadalupe (établie en 1914 et à majorité hispanique). Sous l'épiscopat de Thomas Tschoepe, les deux paroisses finissent par fusionner sous le vocable de Notre-Dame de Guadalupe. En 1975, l'ancienne église paroissiale du même nom, située sur Harwood street, ferme ses portes, les fidèles se rendant désormais aux offices célébrés en la cathédrale. Celle-ci prend officiellement le nom de Notre-Dame de Guadalupe le 12 décembre 1976 .
Elle est l'une des deux seules cathédrales des États-Unis à être placées sous l'invocation de la sainte patronne des Amériques avec la cathédrale de Dodge City (Kansas).
