From the perspective of the development trend of global oil and gas exploration, natural gas exploration in deep and ultra-deep strata has become the main battlefield of fossil energy exploration. Not only conventional carbonate and clastic gas accumulation, but also unconventional shale gas and coal bed methane are being sought in deep to ultra-deep strata. In the early stage, China has formed several pioneering theories and technologies in deep natural gas exploration, which have guided many strategic commercial discoveries and enhanced China’s energy security capabilities. But at the same time, when facing deeper exploration targets, we are also facing new challenges in geology and engineering, and there are still many world-class problems to tackle. The achievements in exploration of the carbonate, clastic rocks, shale gas, coalbed methane and other fields in deep to ultra-deep strata are systematically reviewed in this paper, and the research progress of natural gas accumulation theory in different fields of deep to ultra-deep strata is summarized. In order to provide reference for accelerating deep to ultra-deep natural gas exploration, the main problems and development suggestions are put forward, in the view of resource evaluation, reservoir development and maintenance mechanisms, gas accumulation and enrichment, geophysics and engineering technology.