The most economically important group of species in the genus Amaranthus is the A. hybridus species complex, including three cultivated grain amaranths, A. cruentus, A. caudatus, and A. hypochondriacus, and their putative wild progenitors, A. hybridus, A. quitensis, and A. powellii. Taxonomic confusion exists among these closely related taxa. Internal transcribed spacer (ITS) of nuclear ribosomal DNA, amplified fragment length polymorphism (AFLP), and double-primer fluorescent intersimple sequence repeat (ISSR) were employed to reexamine the taxonomic status and phylogenetic relationships of grain amaranths and their wild relatives. Low ITS divergence in these taxa resulted in poorly resolved phylogeny. However, extensive polymorphisms exist at AFLP and ISSR loci both within and among species. In phylogenetic trees based on either AFLP or ISSR or the combined data sets, nearly all intraspecific accessions can be placed in their corresponding species clades, indicating that these taxa are well-separated species. The AFLP trees share many features in common with the ISSR trees, both showing a close relationship between A. caudatus and A. quitensis, placing A. hybridus in the same clade as all grain amaranths, and indicating that A. powellii is the most divergent taxon in the A. hybridus species complex. This study has demonstrated that both AFLP and double-primer fluorescent ISSR have a great potential for generating a large number of informative characters for phylogenetic analysis of closely related species, especially when ITS diversity is insufficient.