This paper studies the nature of the effective velocity boundary condition for liquid flow over a plane boundary on which small free-slip islands are randomly distributed. It is found that an effective Navier partial-slip condition for the velocity emerges from a statistical analysis valid for arbitrary fractional area coverage β. As an example, the general theory is applied to the low-β limit and this result is extended heuristically to finite β with a resulting slip length proportional toaβ/(1 − β), whereais a characteristic size of the islands. A specification of the nature of the free-slip islands is not required in the analysis. They could be nano-bubbles, as suggested by recent experiments, or hydrophobic surface patches. The results are also relevant for ultra-hydrophobic surfaces exploiting the so-called ‘lotus effect’.