Understanding and predicting the main controls on the sealing capacity of carbonate cap rocks is of great significance for ultradeep carbonate reservoir exploration and production. This study focuses on revealing the pore networks and sealing capacity of the Ordovician carbonate cap rocks in the Tarim Basin by analyzing samples from outcrop analogues using optical and scanning electron microscopy and a combination of mercury intrusion capillary pressure and nitrogen gas adsorption. Three classes of cap rocks are defined here according to their pore-throat structure, fractal dimension, and sealing capacity. These carbonate cap rocks are dominated by limestones and dolomitic limestones. Four pore types are identified: microfractures, intragranular, intercrystalline, and intracrystalline. Six pore structure types show multiscale variability from macropores to micropores. The pore structures present multiple fractal behaviors, with fractal dimensions showing an increasing trend as the pore diameter decreases. The cover coefficient, a parameter that allows characterization of the caprock sealing performance, shows an increasing trend along with increasing the fractal dimension of pore structure. The average cover coefficients of six pore structure types not only show good correlations (either exponential or linear) with certain fractal dimensions, but they also demonstrate a strong positive correlation with the average fractal dimension. These results suggest that the sealing capacity of the studied rocks increases with increasing fractal dimension. The sealing performance of cap rocks significantly decreases with an increasing amount of macropores. This work provides a relevant case study for further understanding of pore structures and sealing capacity of carbonate cap rocks.