To ensure the safe recovery of the black-start system and well synthesize the quick search and local search of multi-objective optimization method, an extended black-start multi-objective optimization method based on virus evolution improved NSGA-II algorithm considering power support and restoration security margin comprehensively is proposed. The optimization goals are designed to maximize the total weighted power generation output (MWh) of the black-start system, to maximize voltage stability margin and to maintain bus voltage at a satisfactory level. Biological virus mechanism and the infection-based operation are introduced into the chromosome of the fast and elitist non-dominated sorting genetic algorithm (NSGA-II). Horizontal infection of the virus is applied to improve local search capability in solution space and avoid the frontier degradation. The virus evolution improved NSGA-II algorithm and the Dijkstra algorithm are employed to solve the Pareto-optimal solutions of the extended black-start schemes. The effectiveness of the proposed method is validated by the optimization results on the New England 10-unit 39-bus power system and the southern power system of Hebei province. The method can provide decision-makers with greater choice of space and guarantee the extended initial black-start power system to recover more power generation output safely and reliably.