This paper proposes a novel algorithm for multiple unmanned aerial vehicles (multi-UAV) cooperative search-attack missions operated in uncertain environments. A parallel decoupling self-planning search-attack algorithm (PDSPSA) is designed to solve the uncertainty of the mission environment and the coupling of the search-attack. To this end, the proposed algorithm can be divided into four modules: a Beta distribution-based probability map module to obtain more information in uncertain environments, a distributed ant colony optimization algorithm (ACO)-based cooperative search module, a Dubins curve-based waypoints online optimization module, and a reward estimation-based parallel decoupling module. Therefore, the threat avoidance algorithm in the online optimization module is designed for possible threat areas and information exchange to update the feasible trajectory, and the parallel decoupling module based on reward estimation is composed of a short-term reward and expected future reward with a heuristic basis. Finally, the stability and effectiveness of the proposed algorithm are evaluated through both simulations and physical experiments. Its performance is further confirmed by comparison with alternative algorithms commonly employed in the multi-UAV cooperative search-attack coupling problem.