Gap-graded granular soils are used as construction materials worldwide, and their hydraulic conductivity depends on their relative content of coarse and fine grains, initial conditions, and particle shape. In this study, a series of constant head hydraulic conductivity tests were performed on gap-graded granular soils with different initial relative densities, fine contents, and particle shapes. The test results show that the hydraulic conductivity decreases with an increase in fine fraction and then remains approximately constant beyond the “transitional fine content.” The role of the structural effect on the hydraulic conductivity is different from that on the mechanical properties (such as stiffness and shear strength). This can be attributed to the degree of filling within inter-aggregate voids, disturbance of soil structure, and densified fine bridges between coarse aggregates. The equivalent void ratio concept was introduced into the Kozeny–Carman formula to capture the effect of fines (aggregates) on the “coarse-dominated” (“fine-dominated”) structure, and a simple model is proposed to capture the change of hydraulic conductivity of gap-granular soils. The model incorporates a structural variable to capture the effect of fines on “coarse-dominated” structure and coarse aggregates on “fine-dominated” structure. The performance of the model was verified with experimental data from this study and previously reported data compiled from the literature. The results reveal that the proposed model is simple yet effective at capturing the hydraulic conductivity of gap-graded granular soils with a wide range of fine contents, initial conditions, and particle shapes.