The inverse cumulative distribution function (CDF) appears in many important problems such as outage probability calculations in wireless communications. The Nakagami-m inverse CDF is difficult to compute numerically and is known to have no closed form. In this paper, we present a new and useful approximation to the Nakagami-m inverse CDF. The genetic algorithm is applied to optimize the coefficients of the proposed approximation. For typical cases in Nakagami-m wireless communication channels, it is shown through comprehensive computer simulations that the proposed method has high accuracy in most of the region of the exact CDF values.