The mutualistic symbioses between reef-building corals and micro-algae form the basis of coral reef ecosystems, yet recent environmental changes threaten their survival. Diversity in host-symbiont pairings on the sub-species level could be an unrecognized source of functional variation in response to stress. The Caribbean elkhorn coral, Acropora palmata, associates predominantly with one symbiont species (Symbiodinium 'fitti'), facilitating investigations of individual-level (genotype) interactions. Individual genotypes of both host and symbiont were resolved across the entire species' range. Most colonies of a particular animal genotype were dominated by one symbiont genotype (or strain) that may persist in the host for decades or more. While Symbiodinium are primarily clonal, the occurrence of recombinant genotypes indicates sexual recombination is the source of this genetic variation, and some evidence suggests this happens within the host. When these data are examined at spatial scales spanning the entire distribution of A. palmata, gene flow among animal populations was an order of magnitude greater than among populations of the symbiont. This suggests that independent micro-evolutionary processes created dissimilar population genetic structures between host and symbiont. The lower effective dispersal exhibited by the dinoflagellate raises questions regarding the extent to which populations of host and symbiont can co-evolve during times of rapid and substantial climate change. However, these findings also support a growing body of evidence, suggesting that genotype-by-genotype interactions may provide significant physiological variation, influencing the adaptive potential of symbiotic reef corals to severe selection.