||We examine the performance of six estimators of the power-law cross-correlations -- the detrended cross-correlation analysis, the detrending moving-average cross-correlation analysis, the height cross-correlation analysis, the averaged periodogram estimator, the cross-periodogram estimator and the local cross-Whittle estimator -- under heavy-tailed distributions. The selection of estimators allows to separate these into the time and frequency domain estimators. By varying the characteristic exponent of the $\alpha$-stable distributions which controls the tails behavior, we report several interesting findings. First, the frequency domain estimators are practically unaffected by heavy tails bias-wise. Second, the time domain estimators are upward biased for heavy tails but they have lower estimator variance than the other group for short series. Third, specific estimators are more appropriate depending on distributional properties and length of the analyzed series. In addition, we provide a discussion of implications of these results for empirical applications as well as theoretical explanations.