Thánh Phaolô Nguyễn Văn Mỹ sinh vào năm 1798 tại làng Kẻ Non, còn gọi là Sơn Nga, thuộc huyện Thanh Liêm, tỉnh Hà Nam. Cha mẹ ngài là những người rất ngoan đạo. Khi còn nhỏ, Phaolô Mỹ có tên trong sổ bộ giáo xứ là Nguyễn Văn Hựu, còn tại gia đình thì có tên gọi là Hào.
Đến năm 15 tuổi, cậu Mỹ được vào ở trong nhà xứ và được Đức Giám mục đặt tên là Mỹ. Hai năm sau, cha Luật từ xứ Kẻ Đầm xin đưa chú Mỹ về với mình để tập tành làm các công việc trong nhà xứ. Cậu ở với cha Luật được 4 năm thì vào học tiếng Latinh tại tiểu chủng viện Vĩnh Trị. Sau đó, cậu về phụ giúp cha Nghiêm, một linh mục thừa sai, rồi làm việc trong nhà chung cho đến khi Đức Giám mục cử ngài lên xứ Bầu Nọ để giúp cha Phan và cha Tân - hai linh mục thừa sai khác.
Những người từng quen biết thầy Mỹ đều khen ngợi và nể trọng thầy. Bởi vì thầy rất chịu khó làm việc theo bậc của mình, giúp giáo dân tiếp nhận các bí tích, khuyên bảo những người có tội ăn năn hối cải, dẫn dắt những người ngoài đạo tiếp cận và theo đạo Thánh của Thiên Chúa.
Khi quan quân vây bắt làng Bầu Nọ có ý định bắt cha Tân, họ đã bắt được thầy Mỹ cùng với thầy Đường và chú Truật. Đến ngày 18 tháng 12 năm 1838, các quan đưa thầy Mỹ ra xử giảo. Sau khi bị giảo hình, quan giao thi hài cho các giáo dân đem về chôn cất, rồi rút quân về tỉnh. Khi đoàn quân rút đi, các tín hữu đào mộ lấy di hài của thầy bỏ vào chiếu đem về an táng tại làng Kẻ Máy, huyện Cao Mại. Vài năm sau, hài cốt của thầy Phaolô Mỹ được đưa về an nghỉ tại quê nhà Kẻ Non.
Thầy giảng Phaolô Nguyễn Văn Mỹ được phong Chân phước vào ngày 27 tháng 5 năm 1900 và được phong hiển thánh vào ngày 19 tháng 6 năm 1988.