The conventional method for estimation of the parameters of Hidden Markov Model (HMM) based acoustic modeling of speech signals uses the Expectation- Maximization (EM) algorithm. But the EM algorithm is highly sensitive to initial values of model parameters and does not guarantee convergence to a global maximum resulting in non-optimized estimation for the HMM and lower recognition accuracy. We propose a Genetic Algorithm (GA) based EM learning method (GA-EHMM) for estimation of the HMM parameters. GA explores the search space more thoroughly than that of the EM algorithm and enables the EM to escape from many local maxima. A constraint-based approach of GA has been adopted in "GA-EHMM" which directs GA towards promising regions of the search space. Instead of generating the initial GA population randomly, a variable segmentation technique is used in the HMM initialization process. "GA-EHMM" has been tested on the TIMIT [10] speech corpus. Experimental results show that "GAEHMM" obtains better values for the likelihood function as well as higher recognition accuracy than that of the HMM model trained by the standard EM algorithm.