Coral reefs provide a high diversity of habitats, including the often complex structure of reef-building corals themselves. Since these coral microhabitats are constrained spatially, specific phenotypic adaptations of associated species to the geometric structure of corals are expected. In the northern Red Sea, we investigated how the physical structure of 2 Acropora corals influences the size, shape and growth of fishes that live in these corals. Branch length and interbranch distance increased strongly and differentially with colony size in both coral species, making large colonies more suitable for larger fishes. We used traditional and geometric morphometrics to demonstrate that the 2 coral-dwelling gobies Gobiodon histrio (Valenciennes) and G. rivulatus (Rueppell) follow different ontogenetic growth patterns. Adult G. histrio show a dorso-ventrally expanded body combined with a lateral compression, while the wider-bodied G. rivulatus has a smaller maximum body length. The lateral compression enables G. histrio to pass smaller interbranch distances than G. rivulatus of the same body length, as demonstrated in an experiment testing their ability to pass narrow interbranch distances. Measurements of G. histrio revealed a greater increase of body length and mass with coral colony size in Acropora digitifera than in A. gemmifera or other coral species. Outliers in growth rates of the fishes demonstrated that moving to larger corals and/or associating with a larger breeding partner benefits fish growth. Shape-related lateral body size differences provide an explanation why those fishes that are better adapted to certain host corals compete more successfully for these microhabitats. The evolution of different shapes in coral-associated fishes indicates differences in habitat specialization to reef-building corals with different geometries.