Multiple Uninhabited Aerial Vehicles (multi-UAVs) coordinated trajectory replanning is one of the most complicatedglobal optimum problems in multi-UAVs coordinated control. Based on the construction of the basic model of multi-UAVscoordinated trajectory replanning, which includes problem description, threat modeling, constraint conditions, coordinatedfunction and coordination mechanism, a novel Max-Min adaptive Ant Colony Optimization (ACO) approach is presented indetail. In view of the characteristics of multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments,the minimum and maximum pheromone trails in ACO are set to enhance the searching capability, and the point pheromone isadopted to achieve the collision avoidance between UAVs at the trajectory planner layer. Considering the simultaneous arrivaland the air-space collision avoidance, an Estimated Time of Arrival (ETA) is decided first. Then the trajectory and flight velocityof each UAV are determined. Simulation experiments are performed under the complicated combating environment containingsome static threats and popup threats. The results demonstrate the feasibility and the effectiveness of the proposed approach.