The advent of virtualization technology has created a huge potential application for cloud computing. In virtualization, a large hardware resource is often broken down into smaller virtual units. These small units are then provisioned to different clients. However, these services need to be provided in such a way that resources are properly utilized. To achieve this, many of the scheduling, allocation, and provisioning issues of data centers are formulated as optimization problems. The virtual machine placement problem (VMPP) is a typical provisioning problem of data centers. In VMPP, several virtual machine requests are to be hosted on physical machines such that a minimum number of physical machines are used. This work proposes a cuckoo search (CS) inspired algorithm for solving the VMPP. To improve the algorithm�s performance, new cost and perturbation functions are developed. The proposed method was tested on two well-known benchmark datasets. It outperformed the reordered grouping genetic algorithm, best-fit decreasing, first-fit decreasing, and an earlier CS method called multiCSA. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.