Fractal analysis was performed on carbonate core plug samples from the Ordovician Majiagou carbonate reservoirs in the Ordos Basin using mercury intrusion capillary pressure (MICP), nuclear magnetic resonance (NMR), and the x-ray computed tomography (CT) measurements to improve our understanding of the pore structure characteristics. The relationships between pore structure parameters and the fractal dimensions were investigated. The pore systems are dominated by secondary intercrystalline pores and enlarged dissolution pores as well as microfractures. The fractal curves from MICP analysis break into two segments at the Swanson’s parameter. The small pore-throat systems can be described by the fractal theory, whereas pores connected by relatively large throats (greater than the pore-throat radius at the Pittman’s hyperbola’s apex) are not cylindrical in shape, cannot be described by a capillary tube model, and tend to have apparent fractal dimensions larger than 3.0. The fact that the entirety of the capillary curve cannot be fit by a single fractal dimension implies that there are multiple pore systems present with different fractal dimensions. The CT analysis shows that the pores are dispersed in the three-dimensional spaces mainly with elliptical shapes. The NMR measurements are sensitive to pore-body size and MICP probes pore-throat dimensions, the latter being complementary to the pore-body–size distribution. None of the CT, MICP, and NMR techniques provide “right” or “wrong” answers to the pore-throat systems, but they probe different aspects of the pore systems. This study assumes the pore shapes to be spherical in general, and then the fractal dimension is calculated from the NMR transverse relaxation time (T2) spectrum. The fractal dimensions of all the samples are calculated, and the accuracy of the fractal model is verified by the high regression coefficients. Almost all the pore systems can be described by fractal theory, and the fractal dimensions are strongly correlated with the T2 values separating the immovable fluid and the free fluid. Microfractures may bias T2 toward larger values, making it hard to derive fractal dimensions from NMR measurements. The coexistence of small pores (pore radius < 10 μm) and large pores (>50 μm) results in a heterogeneous pore distribution and a high fractal dimension. Reservoir quality increases with the complexity degree of the microscopic pore structure. Conversely, samples that are dominated by small pore systems tend to have a lower fractal dimension and a less complex pore structure.