Open-pollinated Eucalyptus grandis seed orchards have been established in Madagascar. Pollen contamination, mating between relatives and an imbalance in gametic contributions affect the efficiency of seed crop quality in seed orchards on which genetic improvement strategies are based. A set of six microsatellite markers was used to carry out parentage tests on 600 progenies harvested from 30 trees in a seed orchard and to identify open-pollinated mating designs, progeny pedigrees and a high genetic admixture in the seed orchard. The trial, which was planted with those progenies and monitored from 9 to 37 months revealed substantial inbreeding depression effects on growth traits due to selfing. Also observed were quite similar allele distributions for the seed orchard and the pollen cloud. This study demonstrated that marker-assisted breeding by parentage analysis based on microsatellites could improve efficiency in open-pollinated seed orchards used as a breeding population and genetic gain could be expected, along with sufficient genetic stability, during selection cycles.