In recent years, low earth orbit navigation augmentation (LEO-NA) has attracted increasing attention and is expected to become a new addition to global navigation satellite systems (GNSSs). When solving complex constellation design problems, traditional optimization algorithms often fail to achieve satisfactory results and are sensitive to parameter settings. We propose a dynamic multi-objective differential evolutionary algorithm based on elite guidance (DMODE-EG). It can select the evolutionary strategy based on the evolutionary state reflected by elite individuals and dynamically modify evolution parameters. Moreover, to achieve more uniform global coverage, we construct a two-layer Walker constellation model for LEO-NA. Then, we use the DMODE-EG algorithm to solve the corresponding multi-objective optimization problem and obtain the optimal constellation parameters. With the augmentation of this LEO-NA constellation to the BeiDou-3 system, the average position dilution of precision (PDOP) values drop to 1.2-2.0 from 1.5-5.5, and the number of visible satellites increases from 8-10 to 13-18. By contrast, some realistic LEO constellations and constellations designed by other algorithms bring weaker improvements and cannot address the problem of high PDOP values in some regions. In addition, simulation results on standard test sets verify the excellent convergence and stability of the DMODE-EG algorithm.The online version contains supplementary material available at 10.1007/s10291-022-01366-5.