In mutualisms involving a host and symbiotic resident, the nature and strength of their interactions are unlikely to be constant over time or space. The efficacy of such mutualisms can be crucial to the population dynamics of one or both partners, particularly where survival bottlenecks occur at early life stages. In laboratory and field outplant experiments, we explored determinants of the onset of mutualistic interactions between early stages of branching corals and their trapeziid crab partners. We confirm that recently-settled crabs are capable of providing housekeeping services to their young coral partners (as has been reported for older crabs and corals), and the presence of a crab in areas of high sedimentation conferred growth benefits approximately three times as strong compared to low sediment conditions. We also show that recruitment of post-larval crabs to very young corals increases with morphological complexity of the coral, which relates to the ability of the host to provide micro-refugia for its crab symbiont, and indicates the potential for selective pressure for traits that attract and retain crabs during this high mortality bottleneck life stage. These findings provide insight into the recruitment process and ontogenetic constraints that influence the onset of mutualistic interactions between corals and their associated symbionts.