The ability of coral reefs to recover from natural and anthropogenic disturbance is difficult to predict, in part due to uncertainty regarding the dispersal capabilities and connectivity of their reef inhabitants. We developed microsatellite markers for the broadcast spawning gorgonian octocoral Eunicea (Plexaura) flexuosa (four markers) and its dinoflagellate symbiont, Symbiodinium B1 (five markers), and used them to assess genetic connectivity, specificity and directionality of gene flow among sites in Florida, Panama, Saba and the Dominican Republic. Bayesian analyses found that most E. flexuosa from the Florida reef tract, Saba and the Dominican Republic were strongly differentiated from many E. flexuosa in Panama, with the exception of five colonies from Key West that clustered with colonies from Panama. In contrast, Symbiodinium B1 was more highly structured. At least seven populations were detected that showed patterns of isolation by distance. The symbionts in the five unusual Key West colonies also clustered with symbionts from Panama, suggesting these colonies are the result of long-distance dispersal. Migration rate tests indicated a weak signal of northward immigration from the Panama population into the lower Florida Keys. As E. flexuosa clonemates only rarely associated with the same Symbiodinium B1 genotype (and vice versa), these data suggest a dynamic host–symbiont relationship in which E. flexuosa is relatively well dispersed but likely acquires Symbiodinium B1 from highly structured natal areas prior to dispersal. Once vectored by host larvae, these symbionts may then spread through the local population, and/or host colonies may acquire different local symbiont genotypes over time.