Service deployment often needs to guarantee QoS of service compositions for networks which compose services to complete users’ application requests. Because evaluation methods for QoS of service compositions rely on fixed-process-based formal models which are not suitable for dynamic service composition processes in service deployment, current service deployment methods can only guarantee QoS of single service and are insufficient to guarantee QoS of service compositions. In this article, a service deployment method considering application reliability is proposed. First, application reliability is introduced to measure QoS of service compositions and an evaluation method based on application flow is presented. Then a service deployment optimization model with the goal of application reliability is established. To solve this model efficiently, an improved genetic algorithm by a new method generating initial population is adopted. Finally, 5G network case study verifies that the improved genetic algorithm converges quickly and our proposed method significantly outperforms the existing method in terms of application reliability by comparison.