Virtual machine (VM) replication is a critical task in any cloud computing platform to ensure the availability of the cloud service for the end user. In this task, one primary VM resides on a physical machine (PM) and one or more replicas reside on separate PMs. In cloud computing, VM placement (VMP) is a well-studied problem in terms of different goals, such as power consumption reduction. The VMP problem can be solved by using heuristics, namely, first-fit and meta-heuristics such as the genetic algorithm. Despite extensive research into the VMP problem, there are few works that consider VM replication when choosing a VMP. In this context, we proposed studying the problem of optimal VMP considering VM replication requirements. The proposed work frames the problem at hand as a multiobjective problem and adapts a nondominated sorting genetic algorithm (NSGA-III) to address the problem. VM replicas’ placement should consider several dimensions such as the geographical distance between the PM hosting the primary VM and the other PMs hosting the replicas. In addition, to this end, the proposed model aims to minimize (1) power consumption, (2) performance degradation, and (3) the distance between the PMs hosting the primary VM and its replica(s). The proposed method is thoroughly tested on a variety of computing environments with various heterogeneous VMs and PMs, including compute-intensive and memory-intensive environments. The obtained results illustrate the performance disparity between the adapted NSGA-III and MOEA/D methods and other methods of comparison, including heuristic and meta-heuristic approaches, with NSGA-III outperforming other comparison methods. For instance, in memory-intensive and in heterogeneous environments, the NSGA-III method’s performance was superior to the first-fit, next-fit, best-fit, PSO, and MOEA/D methods by 58%, 62%, 64%, 55%, and 31%, respectively.