Arabic Language is one of the most widely-spoken languages in the world, Arabic Speech Recognition is one of the topics that need more attention from the research community. In this paper we use statistical model called Hidden-Markov model (HMM) to develop an efficient phoneme recognition engine for Arabic. An HMM has been trained on ELRA Database using expectation maximization algorithm (EM) and we study the effect of different parameters included in the decoding Algorithm known as Viterbi. The effect of increasing the number of Gaussian Mixtures components is also studied in output density of HMM. Results of each case has been presented and suggestions for enhancing performance have been also introduced.