Finding the safest pair of paths between two specified endpoints \(s\) and \(t\) while accounting for multiple correlated failures is a complex computational challenge with various practical applications. In communication backbone networks, for instance, establishing a secure pair of paths between \(s\) and \(t\) is essential for meeting the high availability standards required by emerging technologies such as autonomous driving, AR/VR applications, or telesurgery. This paper first provides a formal proof of the \(\mathcal {N}\!\mathcal {P}\) -hardness of the task. Then, we introduce the Safest Path Pair Ant Colony Optimization (SPP-ACO) algorithm. This new algorithm is based on the Max-Min Ant System. Numerical tests carried out on real-world datasets demonstrate the proposed method’s effectiveness. The proposed SPP-ACO algorithm typically provides at least as safe paths as the baseline, even outperforming it in a significant share of the parameter settings. This grants a place for the SPP-ACO on the stage of best solutions for safest path pair computation in the presence of correlated failures.