Fault permeability in siliciclastic sedimentary basins at shallow depths (< 3 km) is dominated by the presence, distribution and placement of clay smears. While previous algorithms for the estimation of fault permeability recognize the influence of the clay fraction, they do not include a representation of clay smears arising from physics-based modeling of their attributes, nor do they quantify permeability uncertainty or anisotropy due to varying material arrangements. To bridge this gap, here we introduce PREDICT, a novel algorithm that computes probability distributions for the directional components (perpendicular, strike-parallel and dip-parallel) of the fault-scale permeability tensor. The computation is performed for a given throw window, in which PREDICT represents the main shear zone in 2D. The algorithm requires a set of input parameters that describe the faulted stratigraphy. From these inputs, samples for a set of numerical quantities including fault thickness and layer residual friction angle, critical shale smear factor, permeability and permeability anisotropy are drawn. This allows populating a high-resolution discretization of the fault core with clay smears and sand-based fault materials. The final step consists in permeability upscaling. This process is repeated multiple times, each repetition representing one realization, until the full permeability distribution for each component is obtained. We apply this algorithm to several faulted sequences, and show that fault permeability is controlled by the clay smear configuration and that it typically exhibits multimodal probability distributions—a unique feature of our fault-permeability algorithm.