In accordance with pseudo-testcross strategy, the first genetic linkage map of Eucommia ulmoides Oliv. was constructed by an F1 population of 122 plants using amplified fragment length polymorphism (AFLP) markers. A total of 22 AFLP primer combinations generated 363 polymorphic markers. We selected 289 markers segregating as 1:1 and used them for constructing the parent-specific linkage maps. Among the candidate markers, 127 markers were placed on the maternal map LF and 108 markers on the paternal map Q1. The maternal map LF spanned 1116.1 cM in 14 linkage groups with a mean map distance of 8.78 cM; the paternal map Q1 spanned 929.6 cM in 12 linkage groups with an average spacing of 8.61 cM. The estimated coverage of the genome through two methods was 78.5 and 73.9% for LF, and 76.8 and 71.2% for Q1, respectively. This map is the first linkage map of E. ulmoides and provides a basis for mapping quantitative-trait loci and breeding applications.