The deployment strategy for wireless sensor networks (WSNs) affects the quality of service (QoS). Adopting a reasonable deployment strategy can improve the QoS of WSNs. In this paper, the problem regarding sensor node deployment for WSNs on three-dimensional (3D) terrain is modeled as a multi-objective optimization problem. The coverage rate of the WSNs, their unbalanced energy consumption, and the number of sensor nodes are used as fitness functions for the optimization problem. We propose a non-dominated sorting genetic algorithm based on a Voronoi diagram (VNSGA) for solving the wireless sensor network deployment issue and improving the QoS of WSNs on 3D terrain. The proposed algorithm applies the Voronoi diagram to obtain the node-sensing radius and communication radius, which are suitable for 3D terrain with respect to calculating the fitness function of the optimization problem. The Pareto optimal solution is obtained by retaining the solution close to the reference point. The experiments compare the proposed algorithm with the Multi-Objective Particle Swarm Algorithm (MOPSO) and the Non-Dominated Sorting Genetic Algorithm III (NSGA-III) on two terrains with different ranges. The experimental results show that the proposed algorithm outperforms the comparison algorithm on both terrains with different range sizes. The proposed algorithm can improve the coverage to 97.95% and reduce the imbalance in energy consumption to 9.13% on large range terrain.