Recently, Wireless Mesh Network (WMN) has gained important roles in current communication technologies. It has been used in several applications, which the majorities of them are critical applications such as surveillance and rescue systems. Hence, the WMN attracts a bunch of attention from many researchers. WMN consists of mainly mesh clients (MC) s and mesh routers (MR) s, some of the latter are functionalized by additional functions to serve as internet gateways (IG) s. Thus, most of the network traffic is acting toward IGs. Therefore, the network performance largely depends on the MRs’ placement, especially the IGs. Since the gateway placement problem (GPP) has been proven as NP-Hard. Therefore, finding the optimal resolution is difficult or it takes polynomial time. Thus, finding near optimal solution is essential to improve the net operation. This paper proposes a novel approach to solve this problem using Genetic Algorithm (GA) to achieve a near optimal solution, considering the number of IGs and the number of hops that the packet traverses between the IG and the source/destination MR (MR-IG). The main objective of the proposed approach is to minimize the variation of MR-IG-hop counts (VAR-MRIG-Hop) among MRs to insure that the IGs are placed in the appropriate positions. Finally, we evaluated the proposed algorithm using many generated instances using different parameters (population size, tournament size, crossover type, mutation type), the experimental results had shown that the high convergence rate using different parameters. Moreover, the algorithm has considerable scalability and robustness to solve the GPP in large and small networks as well as the positive significance of VAR-MR-IG-hop in comparison with the AVG-MR-IG-hop on enhancing the network performance.