Common carp (Cyprinus carpio) is an important fish for aquaculture, but genomics of this species is still in its infancy. In this study, a linkage map of common carp based on Amplified Fragment Length Polymorphism (AFLP) and microsatellite (SSR) markers has been generated using gynogenetic haploids. Of 926 markers genotyped, 151 (149 AFLPs, two SSRs) were distorted and eliminated from the linkage analyses. A total of 699 AFLP and 20 microsatellite (SSR) markers were assigned to the map, which comprised 64 linkage groups and covered 5506.9 cM Kosambi, with an average interval distance of 7.66 cM Kosambi. The normality tests on interval map distances showed a non-normal marker distribution. Visual inspection of the map distance distribution histogram showed a cluster of interval map distances on the left side of the chart, which suggested the occurrence of AFLP marker clusters. On the other hand, the lack of an obvious cluster on the right side showed that there were a few big gaps which need more markers to bridge. The correlation analysis showed a highly significant relatedness between the length of linkage group and the number of markers, indicating that the AFLP markers in this map were randomly distributed among different linkage groups. This study is helpful for research into the common carp genome and for further studies of genetics and marker-assisted breeding in this species.