Abstract The next-generation of cloud computing will thrive on how effectively the infrastructure are instantiated and available resources utilized dynamically. Load balancing which is one of the main challenges in Cloud computing, distributes the dynamic workload across multiple nodes to ensure that no single resource is either overwhelmed or underutilized. This can be considered as an optimization problem and a good load balancer should adapt its strategy to the changing environment and the types of tasks. This paper proposes a novel load balancing strategy using Genetic Algorithm (GA). The algorithm thrives to balance the load of the cloud infrastructure while trying minimizing the make span of a given tasks set. The proposed load balancing strategy has been simulated using the CloudAnalyst simulator. Simulation results for a typical sample application shows that the proposed algorithm outperformed the existing approaches like First Come First Serve (FCFS), Round Robing (RR) and a local search algorithm Stochastic Hill Climbing (SHC).