Internet of things (IoT) applications aim to provide access to widespread interconnected networks of smart devices, services, and information. This can be achieved by integrating IoT and cloud computing (CC). By using cloud computing service composition (SC), multiple services from various providers can be combined to meet users’ requirements. However, SC is known for its complexity and is classified as an NP-hard problem; such problems are usually approached using heuristics, such as bioinspired algorithms. This paper aims at developing a bio-inspired algorithm that mimics the behavior of cuckoo birds (which examine the nests of other birds to find eggs similar to their own) to find a composite service that fulfills a user’s request in a multi-cloud environment (MCE). Previous work on cuckoo-inspired algorithms has generally utilized metaheuristics, which try to fit a “good” solution to a general optimization problem. In contrast, we propose a problem-dependent heuristic that considers the SC problem and its particularities in MCE. The proposed algorithm, MultiCuckoo, was thoroughly evaluated based on a well-controlled experimental framework that benchmarks the performance of the new algorithm to other outstanding SC algorithms, including the all clouds combination (ACC) algorithm, base cloud combination (BCC) algorithm, and combinatorial optimization algorithm for multiple cloud service Composition (COM2). The results show that our algorithm is more efficient in terms of decreasing the number of examined services, the composed clouds, and the running time in comparison to the benchmark algorithms.