Theo lời kể của Nhậm Ngã Hành, Đông Phương Bất Bại trong quá khứ là phó giáo chủ Nhật Nguyệt thần giáo dưới quyền giáo chủ của Nhậm Ngã Hành. Nhậm Ngã Hành vì mải mê luyện tập Hấp tinh đại pháp nên đã giao toàn bộ công việc của giáo phái cho Đông Phương Bất Bại. Đông Phương Bất Bại đã quán xuyến rất tốt công việc của giáo phái khiến cho Nhậm Ngã Hành đặc biệt tin tưởng, nhờ đó sử dụng mật kế bắt giữ Nhậm Ngã Hành giam tại hắc lao dưới đáy Tây Hồ, giao cho Giang Nam tứ hữu canh giữ và chiếm ngôi giáo chủ từ tay Nhậm Ngã Hành.
Đông Phương Bất Bại lên nắm chức giáo chủ, lại mải mê luyện Quỳ Hoa bảo điển (là bộ sách võ công có cùng nguồn gốc với Tịch tà kiếm pháp), sau khi "dẫn đao tự cung" trở thành người ái nam ái nữ, vì thế Đông Phương Bất Bại đã bỏ bê công việc của giáo phái khiến cho Nhật Nguyệt thần giáo nội bộ lục đục, chém giết lẫn nhau. Đông Phương Bất Bại không xuất hiện trực tiếp mà thông qua người khác điều hành, sử dụng bừa bãi Tam thi não thần đan khống chế giáo chúng.
Đông Phương Bất Bại sau khi luyện thành Quỳ Hoa bảo điển đã trở thành nhân vật có võ công vô địch thiên hạ, khó ai bì kịp.
Hơn 10 năm sau, Khi Nhậm Ngã Hành nhờ có sự trợ giúp của Hướng Vấn Thiên và Lệnh Hồ Xung thoát ra khỏi hắc lao dưới đáy Tây Hồ đã ngay lập tức lên kế hoạch tiêu diệt Đông Phương Bất Bại. Trong đời Nhậm Ngã Hành thì Đông Phương Bất Bại chính là người mà ông khâm phục nhất, ông đã từng nói rằng:
"Lão phu võ công đã cao thâm, cơ trí cũng hơn người, vẫn cho là trong thiên hạ không còn ai là địch thủ. Chẳng ngờ lại bị Đông Phương Bất Bại chơi một vố cay, suýt nữa mất mạng dưới đáy Tây Hồ, vĩnh viễn không thoát ra được. Đông Phương Bất Bại đã là một nhân vật lợi hại đến thế thì lão phu không khâm phục hắn sao được?"
Mối tình với Dương Liên Đình
Vì Đông Phương Bất Bại luyện Quỳ Hoa bảo điển nên việc đầu tiên là phải "dẫn đao tự cung" (tự thiến bộ phận sinh dục của mình). Do đó, Đông Phương Bất bại dù có võ công tuyệt thế nhưng lại bị trở thành con người ái nam. Đông Phương Bất Bại sống một mình trong tẩm cung như một hoàng hậu, mặc áo phu nhân, cầm kim chỉ, thích trang điểm như con gái, yêu thương một gã tên là Dương Liên Đình. Vì yêu Dương Liên Đình, Đông Phương Bất Bại đã giao toàn bộ quyền hành giáo phái cho anh ta, và nghe lời anh ta tàn sát đồng môn khiến cho giáo phái bị chia rẽ.
Đông Phương Bất Bại sau khi luyện thành Quỳ Hoa bảo điển thì võ công phi phàm, một mình đấu trên cơ với 4 đại cao thủ là Lệnh Hồ Xung, Nhậm Ngã Hành, Hướng Vấn Thiên và Thượng Quan Vân, duy chỉ có Lệnh Hồ Xung học được Độc Cô Cửu Kiếm nên có thể nhìn ra sơ hở của Đông Phương Bất Bại nhưng vì thân pháp của y quá nhanh nên chiêu thức chỉ trúng vào tàn ảnh. Chỉ đến khi Dương Liên Đình bị uy hiếp khiến Đông Phương Bất Bại mất tập trung thì y mới bị đánh bại. Đông Phương Bất Bại trước khi chết cầu xin Nhậm Ngã Hành tha mạng cho Dương Liên Đình nhưng bị từ chối, và đã đâm mù một mắt của Nhậm Ngã Hành trước khi bị Nhậm Ngã Hành kết liễu tính mạng.
Sau khi Đông Phương Bất Bại chết, Nhậm Ngã Hành đã lấy ra bí kíp Quỳ Hoa bảo điển từ trong người Đông Phương Bất Bại và tiết lộ ra rằng chính ông đã gài bẫy Đông Phương Bất Bại bằng việc cho y luyện tập bí kíp quái dị này.