The concept of structural complexity describes the temporal progress of feature values on different time scales. We apply it to audio features with the goal to classify music files into genres using k-Nearest Neighbors and Random Forest. We use a publicly available data set of 1550 music tracks which are labeled as belonging to one of six different genres (or to none of them). The classification models are trained with the help of eight feature sets that describe different musical aspects (chords, harmony, instruments, timbre, etc.) in order to find out which features are best suited to predict these genres using the structural complexity. We apply evolutionary multi-objective feature selection to measure individual contributions of different structural complexity features for each genre to feature sets with the smallest classification errors. We also introduce a new feature chord vector which is shown to perform significantly better on genre classification with the structural complexity method than the chord features used in a previous work. The statistical analysis of time scales and features leads to several recommendations for the setup of feature processing based on structural complexity.