Mantel tests are widely used in ecology to assess the significance of the relationship between two distance matrices computed between pairs of samples. However, recent studies demonstrated that the presence of spatial autocorrelation in both distance matrices induced inflations of parameter estimates and type I error rates. These results also hold for partial Mantel test which is supposed to control for the spatial structures. To address the issue of spatial autocorrelation in testing the Mantel statistic, we developed a new procedure based on spatially constrained randomizations using Moran spectral randomization. A simulation study was conducted to assess the performance of this new procedure. Different scenarios were considered by manipulating the number of variables, the number of samples, the regularity of the sampling design and the level of spatial autocorrelation. As identified by previous studies, we found that Mantel statistic and its associated type I error rate are inflated in simple and partial Mantel tests when both distances matrices are spatially structured. We showed that these biases increased with the number of variables, decreased with the number of samples and were slightly lower for regular than irregular sampling. The new procedure succeeded in correcting the spurious inflations of the parameter estimates and type I error rates in any of the presented scenarios. Our results suggest that studies from several fields (e.g. genetic or community ecology) could have been overestimating the relationship between two distances matrices when both presented spatial autocorrelation. We proposed an alternative solution applicable in every field to correctly compute Mantel statistic with a fair type I error rate.