Modern sugarcane cultivars (Saccharum spp) are highly polyploïd and aneuploid interspecific hybrids (2n = 100-130). Two genetic maps were constructed using a population of 198 progeny from a cross between R570, a modern cultivar, and MQ76-53, an old Australian clone derived from a cross between Trojan (a modern cultivar) and SES528 (a wild Saccharum spontaneum clone). A total of 1,666 polymorphic markers were produced using 37 AFLP primer combinations, 46 SSRs and 9 RFLP probes. Linkage analysis led to the construction of 86 cosegregation groups for R570 and 105 cosegregation groups for MQ76-53 encompassing 424 and 536 single dose markers, respectively. The cumulative length of the R570 map was 3,144 cM, while that of the MQ76-53 map was 4,329 cM. Here, we integrated mapping information obtained on R570 in this study with that derived from a previous map based on a selfed R570 population. Two new genes controlling Mendelian traits were localized on the MQ76-53 map: a gene controlling the red stalk colour was linked at 6.5 cM to an AFLP marker and a new brown rust resistance gene was linked at 23 cM to an AFLP marker. Besides another previously identified brown rust resistance gene (Bru1), these two genes are the only other major genes to be identified in sugarcane so far.