In this paper, a Multi-Objective Extended Genetic Programming (MOEGP) algorithm is developed to evolve the structure of the Hierarchical Flexible Beta Fuzzy System (HFBFS). The proposed algorithm allows finding the best representation of the hierarchical fuzzy system while trying to attain the desired balance of accuracy/interpretability. Furthermore, the free parameters (Beta membership functions and the consequent parts of rules) encoded in the best structure are tuned by applying the hybrid Bacterial Foraging Optimization Algorithm (the hybrid BFOA). The proposed methodology interleaves both MOEGP and the hybrid BFOA for the structure and the parameter optimization respectively until a satisfactory HFBFS is found. The performance of the approach is evaluated using several classification datasets with low and high input dimensions. Results prove the superiority of our method as compared with other existing works.