La paroisse du Sacré Coeur est fondée en 1876 par l'abbé Joseph Rouquette alors vicaire de l'église Notre-Dame de l'Espinasse. L'aménagement d'une église temporaire y fait suite rapidement, en attendant la construction d'un édifice qui se veut simple pour l'abbé Rouquette mais beaucoup plus ambitieux pour l'évêque de Rodez, Mgr Bourret. L'église provisoire occupe alors un ancien Théâtre situé sur l'Esplanade de la Capelle, et fondé en 1864. Deux curés sont successivement chargés du projet de construction par l'évêque : l'abbé Joseph Rouquette, jusqu'en 1886, puis l'abbé Théophile Massabiau (membre de la Société Française d'Archéologie). Afin de l'édifier, des souscriptions sont lancées dès février 1877. Si le vicomte de Bonald participe, les paroissiens sont également sollicités. Ils verront alors leurs noms inscrits sur les colonnes monolithes qu'ils auront permis d'acquérir. Même la cantatrice Emma Calvé donnera un concert, en 1892, dont la recette sera entièrement reversée : son nom, inscrit sur un étiquette sera lui aussi apposé sur une colonnes (dans la 1ère travée).

La construction de l'église débute, en 1887, ex-nihilo, sur une propriété située hors les murs de la ville d'origine médiévale, et appartenant à Dieudonné Lubac (A.M.M.). La propriété est achetée en partie par l'évêque, la somme manquante muant les vendeurs en généreux donateurs. Uniquement élevée grâce aux souscriptions, les prêtres successifs se trouvent aussi parfois en bute aux exigences de l'évêque, qui poussent l'abbé Rouquette à la démission en 1886. Il est remplacé par Théophile Massabiau qui accepte finalement le plan dressé par l'architecte départemental, M. Pons, qui propose une église de plan basilical. Les années 1887-1889 voient la construction des bas-côtés, de la sacristie, des chapelles latérales, du chevet, du transept et des colonnes avec leurs chapiteaux. L'année 1890 est consacrée à l'édification de la croisée de transept. Les travaux de gros-oeuvre s'achèvent l'année suivante par la crypte tandis qu'une nouvelle souscription est lancée pour l'achat du mobilier, notamment celui du chemin de croix ou encore celui des vitraux (du verrier Lachaize). L'inauguration a lieu le 27 septembre 1892, en l'absence du prélat mort en juillet. La consécration ne se fait qu'en juillet 1898. Il faut ensuite attendre 1925 pour la construction des deux clochers au-dessus du massif antérieur et l'installation des cloches, le 17 juillet 1926. C'est l'occasion de rappeler alors le cinquantenaire de la fondation de la paroisse mais aussi de glorifier les morts de la guerre de 1914-1918 auxquels la dédicace du bourdon est consacrée.

Par un acte du 7 septembre 2004, l'Association Diocésaine de Rodez vend l'église du Sacré Coeur à la Ville de Millau. Il est stipulé que "tous les meubles et objets liturgiques sont expressément exclus de la cession et [qu'ils] resteront la propriété de l'Association Diocésaine de Rodez".

Pour Jean Nayrolles, l'église du Sacré-Cœur est le dernier grand monument néo-roman de Millau après l'église Saint-François et le Temple, élevée entre 1887 et 1892. Outre son vocable et ses dates de construction, l'édifice présente bien des points communs avec le Sacré-Cœur de Rodez : il fut dessiné par le même architecte, Henry Pons, offre une ampleur comparable et constitue aussi un chantier du cardinal Bourret.