KEY MESSAGE: The paper proposes and validates a robust method for rapid construction of high-density linkage maps suitable for autotetraploid species. Modern genotyping techniques are producing increasingly high numbers of genetic markers that can be scored in experimental populations of plants and animals. Ordering these markers to form a reliable linkage map is computationally challenging. There is a wide literature on this topic, but most has focussed on populations derived from diploid, homozygous parents. The challenge of ordering markers in an autotetraploid population has received little attention, and there is currently no method that runs sufficiently rapidly to investigate the effects of omitting problematic markers on map order in larger datasets. Here, we have explored the use of multidimensional scaling (MDS) to order markers from a cross between autotetraploid parents, using simulated data with 74-152 markers on a linkage group and also experimental data from a potato population. We compared different functions of the recombination fraction and LOD score to form the MDS stress function and found that an LOD2 weighting generally performed well, including when missing values and genotyping errors are present. We conclude that an initial analysis using unconstrained MDS gives a rapid method to detect and remove problematic markers, and that a subsequent analysis using either constrained MDS or principal curve analysis gives reliable marker orders. The latter approach is also particularly rapid, taking less than 10 s on a set of 258 markers compared to 6 days for the JoinMap software. This MDS approach could also be applied to experimental populations of diploid species.