La paroisse est érigée en 1836[2], ce qui en fait la paroisse la plus ancienne de la ville. Une première église Sainte-Marie est construite en 1835 en rondins. Une deuxième église est construite en 1840 et dédiée à saint Augustin. Elle devient la cathédrale, lorsque le diocèse est érigé en 1857 ; mais elle est détruite par un incendie en 1859. La troisième église est bâtie aussitôt après en architecture néo-gothique d'inspiration française par le R.P. Julien Benoît, et consacrée en décembre 1860 à l'Immaculée Conception.
Cette église, aujourd'hui la plus ancienne de la ville, a connu des altérations et restaurations au cours des années, ainsi la façade est simplifiée en 1949-1950 (la grande rosace disparaît et une nouvelle statue de la Vierge est érigée). Elle mesure 190 pieds de long et 90 pieds de large et ne comporte pas de transept. Sa façade est flanquée de deux tours jumelles surmontées de hautes flèches recouvertes en cuivre après la Seconde Guerre mondiale. Les pinacles et parapets sont ôtés. Les murs extérieurs sont recouverts de pierre calcaire de l'Indiana, toujours dans cette époque de l'après-guerre. Les quatorze baies vitrées présentent des vitraux remarquables de la fin du XIXe siècle de la maison bavaroiseZettler. Les candélabres du maître-autel, offerts par des religieuses françaises pour 4 200 francs de l'époque, ont été commandés sur le modèle de ceux de l'église de la Madeleine de Paris.