In view of the complexity of the evolution of deep-water sedimentary system in Rovuma Basin, East Africa, based on seismic data and drilling data, the sedimentary characteristics and its evolutionary stages of the Paleogene lower Eocene deep-water sedimentary system are analyzed and studied. The results show that two rock types, i.e. clastic rocks and carbonate rocks, are developed in the target layer. Clastic rocks are divided into two types of lithofacies: sand-rich and mud - rich, and the natural gas was found in the sand-rich facies with low argillaceous content and high degree of particle sorting. The diagenesis of the reservoir is not strong, and the pore type is mainly primary intergranular pore. The lithofacies and rock texture maturity are the main factors affecting the quality of the reservoir. The lower Eocene deepwater sedimentary system can be further subdivided into five depositional stages (A, B, C, D, and E). Carbonate clastic flow depositions are developed at stage A , and clastic rocks are developed at stage B-E. The reservoir of stage B is tight because of high content of carbonate rock clasts, and the reservoir quality of stages C, D and E is good. Influenced by the interaction between gravity flows and bottom currents, the sedimentary system is characterized by migration from north to south and evolved from channels to lobes in the late stage when the channels are the main type of sedimentary structural unit. The reservoirs of four natural gas discovery wells in the study area belong to deep-water sedimentary sand bodies of three different stages, and the connectivity between the three sand bodies should be considered in gas reservoir evaluation. Development well locations should be rationally deployed to ensure full development of the gas reservoir.