Gobiid fishes of the genus Gobiodon live in strong association with certain reef-building corals that vary considerably in size and architecture. These fishes hence are excellent model systems for studying evolutionary adaption to specific microhabitats. Using a sample of Gobiodon histrio and G. rivulatus and their most important host corals (Acropora digitifera and A. gemmifera) from the northern Red Sea, we assess (1) how corals that are occupied by gobies differ in their architecture from colonies that are not occupied and (2) how fish body shape is associated with the architecture of their host coral. Fish body shape was assessed by geometric morphometric techniques. Coral measurements included colony size, branch length (BL), and interbranch as well as branch tip distance of adjacent branches, for which we applied a new and non-destructive measurement technique based on casts of two-component epoxy resin. The most important factor influencing the occupation of corals was a BL of more than 5 cm. The distance between coral branches was clearly related to the width of the fishes and hence constrained overall fish size. G. histrio and G.rivulatus differ in adult body shape as well in their allometric development of lateral body compression, resulting in different maximum body sizes attainable in the restricted interbranch space of corals. The strong dependence of coral-associated fishes on large coral colonies with specific architectures increases the extinction risk of fishes within deteriorating coral reefs.