This study investigates the multifractal behavior and cross-correlations of major Southeast Asian stock markets, offering valuable insights into their interconnectedness and market dynamics. To achieve this, three methods are applied: the Multifractal Detrended Cross-Correlation Analysis (MF-DCCA), the Q-Cross-Correlation Significance Test, and the DCCA Coefficient Method. Additionally, to assess the contributions to cross-correlation multifractality, the random permutation (shuffling) and phase randomization (surrogate) techniques are employed. The results obtained from the Q-Cross-Correlation statistic reveal significant cross-correlations between all pairs of Southeast Asian indices, emphasizing a strong interconnectedness and shared market dynamics. Furthermore, the DCCA cross-correlation coefficients for the six major indices show persistent cross-correlations, with values ranging from 0 to 1. The fluctuation functions for all pairs demonstrate a nonlinear increase with time scales and scaling exponents, indicating a power-law relationship and confirming the presence of long-range cross-correlations. In addition, the Generalized Hurst Exponent shows a non-linear decrease, while the Rényi Exponent exhibits a non-linear increase as the scaling exponents increase. Meanwhile, the Singularity Spectrum functions display inverted concave parabolic shapes, which further confirm the multifractal nature of the cross-correlations. These findings are corroborated by the non-zero values of the metrics assessing the strength of multifractality, based on the Generalized Hurst Exponent and Singularity Spectrum. Among the pairs, the Indonesia-Malaysia pair demonstrates the highest degree of multifractality, reflecting complex cross-correlations driven by long-range correlations and market-specific factors, whereas the Indonesia-Singapore pair shows the lowest multifractality. Finally, the results of the shuffling and surrogate transformations indicate a significant reduction in multifractality, thereby underscoring the role of long-term temporal cross-correlations and heavy-tailed distributions in the complex behavior of these markets. The findings offer practical implications for portfolio diversification, risk management, and market regulation and policy, emphasizing the importance of multifractal analysis in capturing long-term dependencies and complex dynamics in Southeast Asian stock markets.