Tiếp đến, bằng con đường tự lực, tự nghiên cứu, ông lại là người Việt Nam đầu tiên trong lĩnh vực khoa học cơ bản, bảo vệ thành công và xuất sắc luận án tiến sĩ khoa học toán học Lý thuyết đối hợp bộ n ở Trường đại học Sư phạm Lê-nin (1963). Khi đó, lý thuyết của ông đã được chứng minh và bảo vệ đầy sức thuyết phục và thán phục của một tập thể Hội đồng các nhà khoa học Xô-viết. "... Nguyễn Cảnh Toàn là một nhà hình học xạ ảnh thiên tài, tinh thông cả phương pháp tổng hợp lẫn phương pháp giải tích...", GS Gla-gô-lép, người đứng đầu phản biện tập thể của Trường đại học Sư phạm Crúp-xkai-a đã nhận xét như vậy. Cho đến khi hình học siêu phi Ơclit ra đời (1969), khi đó được ông gọi là Lý thuyết các không gian có tuyệt đối động và được chính thức công bố qua một bài báo gửi đăng tại một Hội nghị toán học quốc tế ở Ni-xơ (Pháp, 1970). Bài báo này đã được đăng trong kỷ yếu của hội nghị năm 1971. Suốt quãng thời gian tiếp theo, cho đến khi trở thành một lý thuyết mới, có đầy đủ cơ sở, đã được ông tổng hợp và thay cái tên mới: Hình học siêu phi Ơclit (bài tổng quan bằng tiếng Pháp về lý thuyết này đã đăng trong Tạp chí Acta Mathematica, năm 1988, tập 13, số 1, trang 117 - 151).