In recent years, several cloud services have proliferated that conspicuously result in providing similar services having same functionality by multiple service providers, but varying in Quality of Service (QoS) properties. Thus, providing a cloud service composition with optimal QoS values that satisfy the requirements of an user becomes complex and challenging in a cloud environment. Several metaheuristics proposed in solving this problem. However, many of them fail to maintain a suitable balance between exploration and exploitation. We propose a novel Eagle Strategy with Whale Optimization Algorithm (ESWOA) that ensures the proper balance between exploration and exploitation.