The implementation of Bus Rapid Transit (BRT) is intended to provide higher-quality services and significantly improve rider satisfaction. Previous studies have investigated rider satisfaction and its determinants to improve BRT services as well as the comparison between BRT and conventional bus/rail transit regarding the rider satisfaction. However, many of previous studies have assumed that service attributes have linear and symmetric influences on rider satisfaction, and among the very few studies that capture the non-linear or asymmetric relationship, there is no combination of different methods to achieve the advantages of both. Besides, to our knowledge, no previous studies have examined changes in the performance and importance of different service attributes after BRT implementation. This paper analyzes the QualiÔnibus rider satisfaction survey data in Belo Horizonte, Brazil, and compares rider satisfaction and the importance of service attributes to overall satisfaction across three cases: two years prior to the BRT implementation, one year after the BRT was implemented, and four years after the BRT implementation. A combination of the ordinal logit regression (OLR) approach and random forest (RF) approach is adopted, which enables a nonlinear relationship between service attributes and rider satisfaction, considers the impact effect size in determining the importance of service attributes, and captures the attitudinal randomness of different riders when rating their satisfaction. Our results show that “expenses with public transport” (i.e. fares) should be addressed first among all the attributes, and the improvement priorities of “speed”, “reliability” and “customer service” increased after the BRT opening. These findings can help policymakers fine-tune improvement strategies targeted at different types of services.