Increasing complexity of physical structure in an environment creates a greater diversity of resources, and results in higher species diversity. This pattern begs an explanation, but quantifying physical complexity is difficult. Most measures are intrinsic to particular ecosystems, but this system-specificity precludes general tests of hypotheses and comparisons among ecosystems. A 'universal' method for quantifying physical complexity is a measure called the fractal dimension, which has values lying between the well-known dimensions of 1, 2 or 3 (line, surface and volume). Fractal dimensions are increasingly used in aquatic ecology to describe complexity of patterns. Various geomorphological aspects of river channels are known to be fractal, but few studies have examined physical features that have direct ecological consequences. Emergent rocks are essential egg-laying sites for many stream insects and thus are vital resources for their populations. Previous research shows that insect abundance and diversity varies with the supply of emergent rocks over some scales. In this study, we tested whether the spatial distribution of emergent rocks can be described as fractal over long stream lengths (~700-1000 m), in seven streams across two countries (Australian and Scotland). Fractal dimensions ranged between ~0.7 and 1.0, which reflected regional differences in lithology, particle size and shape (platy-shaped sedimentary rocks vs. more equant or spherical igneous rocks), and also channel-specific constraints on the development of longitudinal structure (e.g. interruptions to riffle-pool sequences). Our findings therefore illustrate the utility of fractals for capturing variation in physical structure in the environment, enabling appropriate comparison across streams and countries. Importantly, fractal dimensions were constant for each river over two to three orders of magnitude, which suggests that the distribution of emergent rocks will appear consistent to flying insects at the scales over which they search.