Để có vị trí đắc địa xây nhà thờ Đức Bà, phía Công Giáo phải tham gia bốc thăm với nhà cầm quyền Pháp cùng phía tôn giáo khác và cả hai lần họ đều được chọn.
Ngay sau khi chiếm Sài Gòn, năm 1860 chính quyền Pháp cho lập nhà thờ để làm nơi hành lễ cho người Pháp theo đạo Công giáo. Ngôi nhà thờ đầu tiên được lập ở đường Số 5 (nay là đường Ngô Đức Kế, quận 1) – vốn là công trình bỏ hoang vì chiến tranh được tu sửa lại.
Ngôi nhà thờ đầu tiên quá nhỏ, 3 năm sau, ngày 28/3/1863, Đức cha Lefebvre (Đức cha Ngãi) tổ chức lễ đặt viên đá đầu tiên xây dựng một ngôi nhà thờ khác bên bờ Kinh Lớn (còn gọi là kinh Charner, nay là đường Nguyễn Huệ).
Nhà thờ được dựng bằng gỗ cách sông Sài Gòn khoảng 500 m, hoàn thành vào năm 1865 mang tên Nhà thờ Saigon. Về sau, do gỗ bị mối mọt tấn công, các buổi lễ được tổ chức trong phòng khánh tiết của Dinh Thống Đốc cũ (năm 1874 thành trường học Taberd, nay là trường chuyên Trần Đại Nghĩa).
Sau khi được bổ nhiệm phụ trách giáo phận Sài Gòn, Đức Giám mục Colombert nghĩ tới việc xây ngôi nhà thờ mới kiên cố, xứng đáng với vị trí của Sài Gòn lúc bấy giờ, thay thế cho ngôi nhà thờ chính tòa cũ (nhà thờ Saigon) và được chính quyền đồng ý.
Tháng 8/1876, Thống đốc Nam kỳ Duperré tổ chức kỳ thi vẽ đồ án thiết kế nhà thờ mới. Vượt qua 17 thiết kế khác, đồ án của kiến trúc sư J. Bourad với kiến trúc theo kiểu Roman cải biên pha trộn nét Gotich đã được chọn. Địa điểm xây dựng ban đầu được đề nghị ở 3 nơi: góc đường Lê Duẩn và Hai Bà Trưng (nay là Lãnh sự quán Pháp); khu Kinh Lớn (tại vị trí nhà thờ cũ, nay là tòa nhà Sunwah ở đường Nguyễn Huệ) và vị trí hiện nay.
Về địa điểm được chọn (hiện là số 1 Công trường công xã Paris), do nằm ở vị trí đắc địa nên đã xảy ra tranh chấp của nhiều phía. Theo sách “Sưu tầm những họ đạo cổ xưa của Sài Gòn, Địa phận Tây Đàng Trong, năm 1992”, cha Phaolô Đoàn Quang Đạt, năm 1940 khi là cha sở Họ Bà Rịa từng kể rằng, phía nhà cầm quyền Pháp muốn xây cất Nhà hát Thành Phố và một tôn giáo khác cũng muốn xây trụ sở cùng vị trí mà phía Công Giáo đã chọn.
Sau thời gian tranh cãi, chính quyền đành phải bốc thăm công khai. Về phía Công Giáo, Đức Cha Colombert yêu cầu giáo dân toàn địa phận ăn chay cầu nguyện để có thể có được khu đất này. Đến ngày, phía Công Giáo bốc thăm trước và trúng thăm được chọn. Tuy nhiên, do có ý kiến phản đối nên việc bốc thăm phải tổ chức lại. Lần này, nhà cầm quyền Pháp giành bốc thăm trước, kế đến là phía tôn giáo kia nhưng thăm được chọn vẫn thuộc về phía Công giáo.
Nhà thờ Đức Bà được xây như thế nào
Để chuẩn bị cho việc khởi công xây dựng nhà thờ, Đô đốc Duperré cho đấu thầu việc xây dựng thánh đường và cũng kiến trúc sư J. Bourad là người trúng thầu, trực tiếp giám sát công trình. Ngày 7/10/1877, lễ đặt viên đá đầu tiên nhà thờ Đức Bà Sài Gòn do giám mục Isidore Colombert chủ trì dưới sự chứng kiến của phó soái Nam kỳ và các nhân vật tai mắt của Sài Gòn, diễn ra rất long trọng.
Sau 3 năm xây dựng, ngày 11/4/1880 dưới sự chứng kiến của Thống đốc Nam kỳ Le Myre de Vilers, giám mục Colombert đã khánh thành nhà thờ Đức Bà Sài Gòn với tên nhà thờ Nhà nước do toàn bộ chi phí xây dựng và trang trí nội thất đều do chính quyền Pháp tài trợ với số tiền 2,5 triệu France Pháp, tương đương 500.000 đồng Đông Dương thời bấy giờ.
Việc xây dựng nhà thờ này cũng rất đặc biệt, toàn bộ các vật liệu từ ximăng, sắt thép đến ốc vít đều mang từ Pháp sang, công nhân xây cất được chọn trong số thợ lành nghề người Công Giáo. Mặt ngoài công trình xây bằng loại gạch đặt làm tại Marseille để trần, không tô trát, không bám bụi rêu (đến nay vẫn còn màu sắc hồng tươi). Toàn bộ thánh đường có 56 ô cửa kính màu do hãng Lorin của tỉnh Chartres sản xuất.
Móng của thánh đường được thiết kế đặc biệt, chịu được tải trọng gấp 10 lần toàn bộ kiến trúc ngôi nhà thờ nằm bên trên. Đặc biệt, nhà thờ không có vòng rào hoặc bờ tường bao quanh như các nhà thờ quanh vùng Sài Gòn – Gia Định lúc ấy và bây giờ.
Nội thất thánh đường được thiết kế thành một lòng chính, hai lòng phụ tiếp đến là hai dãy nhà nguyện. Toàn bộ chiều dài thánh đường là 93 m. Chiều ngang nơi rộng nhất là 35 m. Chiều cao của vòm mái thánh đường là 21 m. Sức chứa của thánh đường có thể đạt tới 1.200 người.
Bàn thờ nơi Cung Thánh (trung tâm của nhà thờ – nơi linh mục cử hành thánh lễ) được làm bằng đá cẩm thạch nguyên khối có hình 6 vị thiên thần khắc thẳng vào khối đá đỡ lấy mặt bàn thờ. Hệ thống ánh sáng tự nhiên trong nhà thờ êm dịu, mặt tiền nhìn thẳng ra sông Sài Gòn, gió thổi hun hút nên người bên trong nhà thờ luôn rất dễ chịu. Hai tháp lúc đầu không có phần cao nhọn lên mà ngang bằng giống kiểu nhà thờ Đức Bà Paris (Pháp).
Năm 1895, nhà thờ xây thêm hai tháp chuông, mỗi tháp cao 57,6 m và hai tháp có 6 chuông đồng lớn nặng 28,85 tấn. Trên đỉnh tháp có đính cây thánh giá cao 3,5 m, ngang 2 m, nặng 600 kg. Tổng thể chiều cao từ mặt đất lên đỉnh thánh giá là 60,5 m.
Mặt trước thánh đường là một công viên (Công trường Công xã Paris) với bốn con đường giao nhau tạo thành hình thánh giá (biểu tượng của đạo Công giáo). Trung tâm của công viên là bức tượng Nữ vương Hòa bình do nhà điêu khắc G. Ciocchetti thực hiện năm 1959 đưa từ Ý sang. Tượng cao 4,6 m, nặng 8 tấn, bằng đá cẩm thạch trắng của Ý, được tạc với chủ đích để nhìn từ xa nên không đánh bóng. Vì vậy mà toàn thân tượng, kể cả vùng mặt vẫn còn những vết điêu khắc thô.
Sau gần 140 năm hình thành, nhà thờ Đức Bà trở thành công trình kiến trúc biểu tượng của Sài Gòn. Do nằm ở trung tâm quận 1, lại là nhà thờ Chánh tòa của Tổng giáo phận TP HCM nên đây là địa điểm người dân thường tập trung về vào các dịp lễ, Tết, nhất là Noel.
Ngày thường, khu vực quanh nhà thờ Đức Bà là địa điểm quen thuộc của nhiều bạn trẻ và cũng là nơi cô dâu, chú rể đến chụp ảnh cưới. Không chỉ người dân thành phố, nhà thờ Đức Bà còn là điểm tham quan của rất nhiều khách du lịch quốc tế. Mỗi ngày có hàng trăm đoàn khách nước ngoài đến tham quan, dự lễ tại thánh đường này.
Theo Tổng giáo phận TP HCM, nhìn bề ngoài công trình vẫn rất chắc chắn và vững chãi. Tuy nhiên, nhiều hạng mục của nhà thờ đã xuống cấp nặng, cần được sửa chữa. Vì vậy, Tổng giáo phận đang làm việc với các sở, ngành để lên kế hoạch đại trùng tu ngôi thánh đường này.