Sau khi thi đậu Tú tài vào năm 1932, cô gái miền Nam theo chuyến tàu của hãng Messagerie Maritime trở về nước. Tình cờ trên chiếc tàu nầy có ông vua Việt Nam hồi loan sau khi hoàn tất việc học, đó là vua Bảo Đại mà hồi đó giới sinh viên ở Pháp thường gọi một cách thân mật là Prince Vĩnh Thụy. 

Tuy cùng trên một chiếc tàu bồng bềnh giửa đại dương một thời gian khá lâu nhưng Nguyễn Hữu Thị Lan chưa có cơ hội làm quen với vị Vua trẻ tuổi. Mãi cho đến gần một năm sau, nhân dịp vua Bảo Đại nghỉ mát tại Đà Lạt và do sự sắp đặt của Toàn quyền Đông Dương, viên Đốc Lý (tức Thị Trưởng sau nầy) thành phố Đà Lạt tổ chức một buổi dạ tiệc tại khách sạn Palace (sau gọi là khách sạn Langbian) để tìm cách cho hai người gặp nhau. Tối hôm đó, trong chiếc áo lụa màu thiên thanh, Nguyễn Hữu Thị Lan đã xuất hiện trước Hoàng đế Bảo Đại để rồi chiếm gọn trái tim của một người có địa vị cao nhất nước. 

Tưởng cũng nên nói thêm là trước đây có nhiều nguồn tin nói rằng vua Bảo Đại đã gặp Marie Thérèse trên chuyến tàu thủy từ Pháp về Việt Nam, nhưng căn cứ vào hồi ký của vua Bảo Đại và tiết lộ của Hoàng hậu Nam Phương được chúng tôi trích dẫn dưới đây thì hai người đã gặp nhau trong một hoàn cảnh khác. 

Nhờ tòng học ở một trường thuộc nhà Dòng, được các nữ tu chỉ dạy các lễ nghi Tây phương đối với Vua Chúa nên tối hôm đó, lúc vừa diện kiến vua Bảo Đại, Nguyễn Hữu Thị Lan đã quỳ một gối và cúi đầu sát mặt đất để tỏ lòng tôn kính nhà Vua. Lẽ tất nhiên, một vị vua trẻ tuổi và hào hoa như vua Bảo Đại thì làm sao ông có thể không xiêu lòng trước sắc đẹp mỹ miều của Nguyễn Hữu Thị Lan. Và chuyện sẽ đến đã đến: đám cưới của vị thiếu quân hào hoa với một nữ lưu tràn trề hương sắc miền Nam đã diễn ra tại Huế ngày 20-3-1934. Ngay ngày hôm đó Nguyễn Hữu Thị Lan được tấn phong làm Hoàng hậu với danh hiệu Nam Phương. 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 bà vợ Vua thuộc triều Nguyễn. Vì mười hai đời vua Nguyễn trước kia, các bà vợ Vua chỉ được phong tước Vương phi, đến khi chết mới được truy phong Hoàng hậu. 

Nhắc đến cuộc nhân duyên với Hoàng hậu Nam Phương, cựu hoàng Bảo Đại đã ghi lại 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. Cô ta 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 (tức vua Gia Long) đã đượ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 ". 

Về phần Hoàng hậu Nam Phương, bà đã nhắc lại "cái thuở ban đầu lưu luyến ấy" như sau: 

"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 (Lê Phát An là anh ruột bà Nguyễn Hữu Hào) và tôi đến dự dạ tiệc ở Hotel 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 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èsẹ (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 đúng cung cách lễ nghi âu tây đối với Ngài". 

Sau lễ cưới, vua Bảo Đại cùng hoàng hậu Nam Phương 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 vua 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 vua Bảo Đại. 

Tại điện Kiến Trung, Hoàng hậu Nam Phương đã lần lượt hạ sanh 5 người con gồm có: 

-Thái tử Bảo Long, sinh ngày 4-1-1936 

-Công chúa Phương Mai, sinh ngày 1-8-1937 

-Công chúa Phương Liên, sinh ngày 3-11-1938 

-Công chúa Phương Dung, sinh ngày 5-2-1942 

-Hoàng tử Bảo Thắng, sinh ngày 9-12-1943 

Thường ngày, ngoài việc chăm sóc dạy dỗ con cái, thỉnh thoảng hoàng hậu Nam Phương phải cùng các quan ở Bộ Lễ bàn thảo các lễ lạ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à Hoàng thái hậu Từ Cung, tức mẹ vua Bảo Đại. Tóm lại, bà rất chu toàn bổn phận làm dâu.

Ngoài việc quản trị nội cung như đã nói trên đây, hoàng hậu Nam Phương còn tham gia các việc xã hội và từ thiện. Như đi thăm trường nữ Trung học Đồng Khánh ở đường Jules Ferry (tức Lê Lợi sau nầy), bà thường tiếp xúc với các Giáo sư, nhắc nhở họ cố gắng làm tròn thiên chức của một nhà mô phạm; đi thăm Nữ Công Học Hội ở đường Khải Định (tức đường Nguyển Huệ ngày nay). Theo lời nữ sĩ Đạm Phương sau nầy kể lại thì có lần Hoàng hậu Nam Phương 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. 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 Cứu Thế. 

Ngày nay, không ai còn lạ lùng khi trông thấy quý vị đệ nhất phu nhân xuất hiện nơi công cộng để giúp chồng trong việc ngoại giao, nhưng cách đây sáu mươi năm, Hoàng hậu Nam Phương giúp vua Bảo Đại trong việc tiếp kiến các nhà ngoại giao là một điều quý hiếm. Vào thời đó, nhiều người ở kinh đô Huế đều biết trong những lần vua Bảo Đại tiếp đón các quốc khách như Thống Chế Tưởng Giới Thạch của Đài Loan, Quốc Vương Soupha Vangvong Lào quốc hoặc Quốc vương Sihanouk của Cao Mên v.v đều có sự hiện diện của hoàng hậu Nam Phương. Lần vua 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. 

Chi tiết đáng kể nhất là việc Hoàng hậu Nam Phương đã đem lại hòa khí giữa các chức sắc đạo Thiên Chúa ở Việt Nam với Hoàng tộc nhà Nguyễn. Vì như chúng ta đã biết, đạo Thiên Chúa với các vị vua triều Nguyễn vốn có những căng thẳng lịch sử thì Nam Phương hoàng hậu, như một làn gió mát, đã thoa dịu sự căng thẳng lịch sử tưởng chừng như không bao giờ thay đổi. 

Nhân đây, tưởng cũng nên nhắc lại một hành động chứng tỏ lòng thiết tha với quê hương đất nước của Hoàng hậu Nam Phương mà chúng tôi mới tìm thấy trong tài liệu của sử gia Pháp Jean Renaud do nhà xuất bản Guy Boussac ấn hành năm 1949: 

Số là sau khi quân Pháp dựa vào thế lực của quân Anh quốc để gây hấn ở miền Nam với ý đồ tái chiếm thuộc địa Việt Nam. (Xin lưu ý bạn đọc lúc cuộc chiến khởi đầu tại Nam phần là thuần túy giữa thực dân Pháp một bên và một bên là người Việt Nam chống lại sự đô hộ của người Pháp, không giống thực chất cuộc chiến Quốc Cộng sau nầy). Lúc đó vua Bảo Đại đã từ chức, bà Nam Phương đang ở tại An Định cung bên bờ sông An Cựu.