We derived two new expressions for the intrinsic permeability (k) of fractal porous media. The first approach, the probabilistic capillary connectivity (PCC) model, is based on evaluating the expected value of the cross-sectional area of pores connected along various flow paths in the direction in which the permeability is sought. The other model is a modified version of Marshall's probabilistic approach (MPA) applied to random cross matching of pores present on two parallel slices through a fractal porous medium. The Menger sponge is a three-dimensional mass fractal that represents the complicated pore space geometry of soil and rock. Predictions based on the analytical models were compared with estimates of k derived from lattice Boltzmann method (LBM) simulations of saturated flow in virtual representations of Menger sponges. Overall, the analytically predicted k values matched the k values from the LBM simulations with <14% error for the deterministic sponges simulated. While the PCC model can represent variation in permeability due to the randomization process for each realization of the sponge, the MPA approach can capture only the average permeability resulting from all possible random realizations. Theoretical and empirical analyses of the surface fractal dimension (D2) for successive slices through a random Menger sponge show that the mean D2 value 〈D2〉 = D3 − 1, where D3 is the three-dimensional mass fractal dimension. Incorporating 〈D2〉 into the MPA approach resulted in a k that compared favorably with the modal value of k from LBM simulations performed on 100 random realizations of a random Menger sponge.