Polyploid species are extremely important in agriculture. However, the complex structure of their genomes is not well understood. Despite all advances in genetic mapping of autotetraploids, the vast majority of genetic mapping models used for species with high ploidy level, such as sugarcane, are approximations from diploid organisms. Here, we present a novel method to construct genetic linkage maps in autopolyploid species with any ploidy level using hidden Markov models. It can be applied to dominant and codominant markers data, with biallelic or multiallelic behavior. The method is based on the calculation of a general transition matrix for a given ploidy level followed by a reduction of its dimension using a computer- based approach. We illustrate our method using a simulated decaploid mapping population and a real sugarcane dataset derived from a cross between two pre-commercial varieties, scored with SNPs. The results indicate that our method is very efficient in obtaining reliable genetic maps, even for high ploidy levels and for markers with high dosages, particularly when these markers are scored as codominant. Through our model, it was also possible to estimate the multipoint likelihood, the recombination fractions and the linkage phases between all markers. With a properly constructed map, it can be very useful for finding genomic regions associated with variation in quantitative traits, studying the genetic architecture of quantitative traits, and assembling genome sequences. Our model represents a step forward on the understanding of the complex structure of high polyploid genomes.