Arabic phonemes recognition is a very important step in most of Arabic speech recognition based applications. This work presents a recipe for building an efficient Arabic phonemes recognizer with HMMs trained by two databases for Modern Standard Arabic (MSA). HMM parameters such as number of states and number of GMMs per state are optimized. And a comparison between models trained with each database is given. HTK tool has been used in this work and 70.2% maximum recognition rate has been achieved which is very interesting compared with other researches.