Abstract: The dynamic task planning issue of early warning system of Low Earth Orbit (LEO) is described by the system resource and missile tracking task aspects, and the Dynamic Constraint Satisfaction Problem (DCSP) model of system dynamic task planning is built which includes two level indexthe integrative optimizing indexes of tracking precision, task accomplishment, sensor switching and resource slack, the adjusting range of original task planning scheme. To solve the dynamic planning model, a variable neighborhood heuristic algorithm on the basis of original planning and schedule is put forward, and the directly insert, redistribute, replace and delete neighborhood structure and their operators are designed in the heuristic algorithm. The simulation results show the leveled dynamic planning model is rational and the heuristic algorithm can solve the dynamic task planning issue of early warning system of LEO effectively.