Về Việt Nam được gần một năm, khi vua Bảo Đại lên nghỉ mát tại Đà Lạt, và được sự dàn xếp của vị Toàn Quyền Pháp Pasquier và viên Đốc lý Darles (Thị Trưởng) Đà Lạt, trong một buổi dạ tiệc tại khách sạn La Palace tại Đà Lạt do Toàn quyền Đông Dương và viên Đốc lý[7] thành phố sắp đặt, Nguyễn Hữu Thị Lan và Bảo Đại đã gặp nhau.

Về cuộc tình duyên đó, Bảo Đại có viết trong cuốn Con rồng Việt Nam:

"Sau lần hội ngộ đầu tiên ấy, thỉnh thoảng chúng tôi lại gặp nhau để trao đổi tâm tình. Marie Thérèse thường nhắc đến những kỉ niệm ở trường Couvent des Oiseaux một cách thích thú. Cũng như tôi, Marie Thérèse rất thích thể thao và âm nhạc. Nàng có vẻ đẹp dịu dàng của người miền Nam pha một chút Tây phương. Do vậy mà tôi đã chọn từ kép Nam Phương để đặt danh hiệu cho nàng. Các vị Tiên Đế của tôi cũng thường hướng về người đàn bà miền Nam. Nếu tôi nhớ không sai thì trước Hoàng hậu Nam Phương, có đến bảy phụ nữ miền Nam đã từng là chủ nhân của Hoàng thành Huế. Khi chọn phụ nữ miền Nam làm vợ, hình như đức Tiên Đế và tôi đều nghĩ rằng trước kia đức Thế Tổ Cao Hoàng đã được nhân dân miền Nam yểm trợ trong việc khôi phục giang sơn. Chính đó là sự ràng buộc tình cảm giữa Hoàng triều Huế với người dân miền Nam".
Hoàng hậu Nam Phương cũng nhắc lại:

"Hôm đó ông Darle, Đốc Lý thành phố Đà Lạt gởi giấy mời cậu Lê Phát An tôi [8] và tôi đến dự dạ tiệc ở Hôtel Palace. Tôi không muốn đi nhưng cậu An tôi năn nỉ và hứa với tôi là chỉ đến tham dự một chút và vái chào nhà Vua xong là về nên tôi phải đi một cách miễn cưỡng và tôi cũng chỉ trang điểm sơ sài và chỉ mặc cái áo dài bằng lụa đen mua bên Pháp thôi. Chúng tôi đến trễ nên buổi tiệc đã bắt đầu từ lâu. Cậu tôi kéo ghế định ngồi ngoài hiên thì ông Darle trông thấy, ông ta chạy đến chào chúng tôi rồi nắm tay cậu tôi kéo chúng tôi vô nhà. Vừa đi ông vừa nói: "Ông và cô phải đến bái yết Hoàng thượng mới được". Khi cánh cửa phòng khách vừa mở, tôi thấy vua Bảo Đại ngồi trên chiếc ghế bành chính giữa nhà. Ông Darle bước tới bên cạnh Vua rồi nghiêng mình cúi chào và kính cẩn nói:
-Votre Majesté, Monsieur Lê Phát An et sa nièce, Mademoiselle Marie Thérèse. (Tâu Hoàng thượng, đây là ông Lê Phát An và người cháu gái, cô Marie Thérèse)
Nhờ các nữ tu ở trường Couvent des Oiseaux từng chỉ dạy nên tôi biết phải làm gì để tỏ lòng tôn kính đối với bậc Quân Vương, vì vậy tôi đã không ngần ngại đến trước mặt Hoàng Đế, quỳ một gối và cúi đầu sát nền nhà cho đến khi thấy bàn tay cậu tôi kéo tôi dậy, tôi mới đứng lên. Vua gật đầu chào tôi đúng lúc tiếng nhạc vừa trỗi theo nhịp điệu Tango, Ngài ngỏ lời mời và dìu tôi ra sàn nhảy rồi chúng tôi bắt đầu nói chuyện.
Về sau, khi đã trở thành vợ chồng, Ngài mới cho tôi biết hôm đó Ngài rất chú ý cách phục sức đơn sơ của tôi. Tôi nghĩ rằng tôi được nhà Vua lưu ý một phần do trong suốt buổi dạ tiệc chỉ có tôi là người đàn bà Việt Nam duy nhất nói tiếng Pháp và theo hành lễ đúng cung cách lễ nghi Âu tây đối với Ngài".
Bảo Đại say mê Nguyễn Hữu Thị Lan, ông viết lại: Lan có một vẻ đẹp thùy mị của người con gái miền Nam, hiền lành và quyến rũ làm tôi say mê. Và khi Bảo Đại hỏi cưới thì gia đình Nguyễn Hữu Thị Lan ra điều kiện:

Nguyễn Hữu Thị Lan phải được tấn phong Hoàng Hậu Chánh Cung ngay trong ngày cưới.
Được giữ nguyên đạo Công giáo, và các con khi sinh ra phải được rửa tội theo giáo luật Công giáo và giữ đạo.
Riêng Bảo Đại thì vẫn giữ đạo cũ là Phật giáo.
Phải được Tòa Thánh cho phép đặc biệt hai người lấy nhau và giữ hai tôn giáo khác nhau.[9]
Vì vậy cuộc hôn nhân giữa Bảo Đại và Nguyễn Hữu Thị Lan gặp phải rất nhiều phản đối. Trước Hoàng Tộc Triều Nguyễn, Bảo Đại đã nói: "Trẫm cưới vợ cho trẫm đâu phải cưới cho cụ Tôn Thất Hân [10] và Triều đình."

Hôn lễ được tổ chức ngày 20 tháng 3 1934 ở Huế. Khi đó Bảo Đại đúng 21 tuổi, còn Nguyễn Hữu Thị Lan 20 tuổi. Ngay ngày hôm sau, lễ tấn phong Hoàng Hậu được diễn ra rất trọng thể ở điện Thái Hòa. Hoàng đế phong Nguyễn Hữu Thị Lan tước vị Nam Phương Hoàng Hậu.

Sự kiện Nguyễn Hữu Thị Lan được tấn phong Hoàng hậu ngay sau khi cưới là một biệt lệ đối với các chính cung trong triều Nguyễn. Vì mười hai đời Tiên Đế nhà Nguyễn trước, các bà chánh cung chỉ được phong tước Hoàng quý phi, đến khi chết mới được truy phong Hoàng hậu. Bắt đầu từ năm 1934, triều đình nhà Nguyễn dùng từ Ngài Hoàng để thưa gởi hoặc nói về Nam Phương Hoàng Hậu.
Bảo Đại có giải thích thêm về hai chữ Nam Phương như sau: "Tôi đã chọn tên trị vì cho bà Hoàng Hậu mới là Nam Phương. Nam Phương có nghĩa là hương thơm của miền Nam (Parfume du Sud) và tôi cũng ra một chỉ dụ đặc biệt cho phép bà được phục sức màu vàng – màu dành riêng cho Hoàng Đế".

Nguyễn Hữu Thị Lan mang quốc tịch Pháp và theo đạo Công giáo. Khi cựu Khâm sứ Trung kỳ là ông bà Charles viết thư xin phép Toà Thánh cho Nam Phương được kết hôn với Bảo Đại và mỗi người giữ đạo riêng. Nhưng Giáo hoàng Piô XI đã không chấp nhận. Việc đã lỡ rồi, nên đám cưới của Bảo Đại với Thị Lan vẫn cứ tiến hành. Vì vậy Giáo hoàng đã rút phép thông công không cho Nam Phương xưng tội và rước lễ như trước khi lấy Bảo Đại. Sau khi kết hôn, Bảo Đại nghe theo lời của vợ chồng Charles là nên tặng huy chương cho mấy Giám mục người Pháp, người Ý và Khâm sứ Toà thánh ở Huế để lấy lòng Toà Thánh thì tương lai sẽ được Toà thành tha phạt vạ bà Nam Phương. Giáo hoàng Piô XI qua đời ngày 10-2-1939, và ngày 12-3-1939 Giáo hoàng Piô XII lên kế vị nên đã xét lại và chấp nhận cho Bảo Đại cứ giữ đạo Phật, còn Nam Phương cứ giữ đạo Công giáo, nhưng các con khi sanh ra phải được rửa tội để nhập đạo Công giáo theo người mẹ là bà Nam Phương. Vì thế, sau đó hai vợ chồng Bảo Đại và Nam Phương đã sang ngay La Mã xin yết kiến để cảm ơn Giáo hoàng Piô XII.[cần dẫn nguồn]

Sau lễ cưới, Bảo Đại cùng Nam Phương hoàng hậu dọn về ở tại điện Kiến Trung thuộc khu vực cấm thành. Điện này xây cất từ thời Khải Định Khải Định, nhưng đã được sửa chữa và tân trang các tiện nghi Tây phương vào đầu triều Bảo Đại.

Đêm ngày 4 tháng 1 năm 1936, người dân Huế nghe những tiếng súng bắn mừng báo tin Nam Phương hoàng hậu đã hạ sinh, và lờ mờ sáng lại một lần nữa 7 tiếng súng thần công làm lay động cả Hoàng Thành, báo hiệu Hoàng hậu đã sinh một Hoàng tử[11]. Người đó chính là Đông cung Thái tử Nguyễn Phúc Bảo Long.

Nam Phương hoàng hậu cùng Bảo Đại có tất cả năm người con:

Nguyễn Phúc Bảo Long, sinh ngày 4 tháng 1 năm 1936, tước phong Hoàng thái tử.
Hoàng nữ Phương Mai, sinh ngày 1 tháng 8 năm 1937.
Hoàng nữ Phương Liên, sinh ngày 3 tháng 11 năm 1938.
Hoàng nữ Phương Dung, sinh ngày 5 tháng 2 năm 1942.
Nguyễn Phúc Bảo Thắng, sinh ngày 9 tháng 12 năm 1943, Nhị hoàng tử.
Khi đó công việc hàng ngày của Hoàng hậu là dạy dỗ các hoàng tử, công chúa. Thỉnh thoảng bà phải cùng các quan ở Bộ Lễ bàn thảo các lễ tiệc trong cung đình, lo việc cúng giỗ các Tiên đế và đi vấn an sức khỏe các bà Tiên cung và Từ Cung Hoàng thái hậu, tức mẹ của Bảo Đại. Hoàng hậu còn tham gia các việc xã hội và từ thiện. Hàng năm bà đều tham dự các buổi phát giải thưởng cho các học sinh giỏi tổ chức tại trung tâm Accueil gần nhà Dòng Chúa Cứu Thế. Theo lời nữ sĩ Đạm Phương thì có lần Hoàng hậu bảo bà làm đơn xin phép Bộ Giáo dục đem môn nữ công gia chánh vào học đường.

Hoàng hậu cũng xuất hiện thường xuyên bên cạnh Bảo Đại trong các nghi lễ ngoại giao như đón tiếp Thống chế Tưởng Giới Thạch của Đài Loan, Quốc Vương Soupha Vangvong nước Lào hoặc Quốc vương Sihanouk của Cao Miên... Lần Bảo Đại tự mình lái xe hơi đi thăm Nam Vang cũng có mặt Hoàng hậu tháp tùng. Là người Công giáo, hoàng hậu đã đem lại hòa khí giữa các chức sắc đạo Công giáo ở Việt Nam với Hoàng tộc nhà Nguyễn, vốn trước đó có những quan hệ căng thẳng kéo dài.