The genome of modern sugarcane cultivars is highly polyploid (~12x), aneuploid, of interspecific origin, and contains 10 Gb of DNA. Its size and complexity represent a major challenge for the isolation of agronomically important genes. Here we report on the first attempt to isolate a gene from sugarcane by map-based cloning, targeting a durable major rust resistance gene (Bru1). We describe the genomic strategies that we have developed to overcome constraints associated with high polyploidy in the successive steps of map-based cloning approaches, including diploid/polyploid syntenic shuttle mapping with two model diploid species (sorghum and rice) and haplotype-specific chromosome walking. Their applications allowed us (i) to develop a high-resolution map including markers at 0.28 and 0.14 cM on both sides and 13 markers cosegregating with Bru1 and (ii) to develop a physical map of the target haplotype that still includes two gaps at this stage due to the discovery of an insertion specific to this haplotype. These approaches will pave the way for the development of future map-based cloning approaches for sugarcane and other complex polyploid species.