Cost-sensitive learning is one of the most adopted approaches to deal with data imbalance in classification. Unfortunately, the manual definition of misclassification costs is still a very complicated task, especially with the lack of domain knowledge. To deal with the issue of costs' uncertainty, some researchers proposed the use of intervals instead of scalar values. This way, each cost would be delimited by two bounds. Nevertheless, the definition of these bounds remains as a very complicated and challenging task. Recently, some researches proposed the use of genetic programming to simultaneously build classification trees and search for optimal costs' bounds. As for any classification tree there is a whole search space of costs' bounds, we propose in this paper a bi-level evolutionary approach for interval-based cost-sensitive classification tree induction where the trees are constructed at the upper level while misclassification costs intervals bounds are optimized at the lower level. This ensures not only a precise evaluation of each tree but also an effective approximation of optimal costs intervals bounds. The performance and merits of our proposal are shown through a detailed comparative experimental study on commonly used imbalanced benchmark data sets with respect to several existing works.