Music is one of the biggest issues in the world because of its importance and association with different aspects of us like Religion, Health, Culture etc. Besides to that large numbers of musical productions are introduced and released in different forms; diverse music file categorization techniques are also on being introduced for facilitating the task of archiving and other musical record management tasks. This study is then proposed to minimize the challenges of categorizing the Ethiopian polyphonic musical records in to their corresponding genres based on their scale structure through techniques of Machine Learning; by making its primary focus on selecting the appropriate sample records, identifying best representative features and classification algorithms. The experiments are run on the four well known Ethiopian pentatonic scales which are Ambasel, Anchihoya, Bati and Tizita. A total of 710 sample records are used for the experimentation; 310 samples from the Ethiopian Orthodox church songs and 400 secular samples records. Music genre classification task has two main stages feature extraction and classifier (model) building. In this research a total of audio features were extracted from the new Ethiopian music dataset 45 distinct features are extracted from each sample. Most of the features are from tonality feature because, according to Ezra abate and other Ethiopian music expert‟s suggestion and preliminary experiment made during feature selection stage of this study to determine which features can help to better differentiate the Ethiopian pentatonic scale class the tonality features are found more distinctive. More than 36 of the total features are tonality features and the remaining 9 features are timbre features. Alteration tools used in the feature extraction process is taken from MAHLAB MIR toolbox. The experiment is done on the dataset of features extracted from the first 30 seconds segment of the audio record and with full song of 50 minutes and the three learning algorithms SVM, ANN and Decision tree are employed. the best classification accuracy 86.96% is gained with SVM model with features extracted from 310 full records of Ethiopian orthodox Tewahido church songs.