This paper presents a new Genetic Algorithm-based Energy-Efficient adaptive clustering hierarchy Protocol (GAEEP) to efficiently maximize the lifetime and to improve the stable period of Wireless Sensor Networks (WSNs). The new protocol is aimed at prolonging the lifetime of WSNs by finding the optimum number of cluster heads (CHs) and their locations based on minimizing the energy consumption of the sensor nodes using genetic algorithm. The operation of the GAEEP is broken up into rounds, where each round begins with a set-up phase, when the base station finds the optimum number of CHs and assigns members nodes of each CH, followed by a steady-state phase, when the sensed data are transferred to CHs and collected in frames; then these frames are transferred to the base station. The performance of the GAEEP is compared with previous protocols using Matlab simulation. Simulation results show that GAEEP protocol improves the network lifetime and stability period over previous protocols in both homogeneous and heterogeneous cases. Moreover, GAEEP protocol increases the reliability of clustering process because it expands the stability period and compresses the instability period.