The Albertine Graben in western Uganda is a Mesozoic-Cenozoic rift basin with petroleum exploration potential. A fundamental evaluation of petroleum potential of the graben is given based on field research, data processing of gravity and magnetism, analysis of graben structure, geochemistry, reservoir and composition research. The basin has a double-layered framework and a large thickness of sediments. Gravity highs shown in a residual anomaly map might indicate central uplift zones. There exist at least two sets of mature or low-maturity source rocks corresponding to a certain source rock in the Cretaceous or Paleogene and Neogene strata. The graben has basement rock with potential reservoirs and Tertiary sandstone reservoirs and thus has petroleum exploration potential.