The aim of this study is to test the freshness of horse mackerels by using a low cost electronic nose system composed of eight different metal oxide sensors. The process of freshness evaluation covers a seals of seven different classes corresponding to 1, 3, 5, 7, 9, 11, and 13 storage days. These seven classes are categorized according to six different classifiers in the proposed binary decision tree structure. Classifiers at each particular node of the tree are individually trained with the training dataset. To increase success in determining the level of fish freshness, one of the k-Nearest Neighbors (k-NN), Support Vector Machines (SVM), Linear Discriminant Analysis (LDA) and Bayes methods is selected for every classifier and the feature spaces change in every node. The significance of this study among the others in the literature is that this proposed decision tree structure has never been applied to determine fish freshness before. Because the freshness of fish is observed under actual market storage conditions, the classification is more difficult. The results show that the electronic nose designed with the proposed decision tree structure is able to determine the freshness of horse mackerels with 85.71% accuracy for the test data obtained one year after the training process. Also, the performances of the proposed methods are compared against conventional methods such as Bayes, k-NN, and LDA.