Considering the relevance of health behaviors for chronic diseases prevalence and mortality and the increase in income concentration observed in the world and in Brazil, this study aimed to evaluate the changes in the prevalence and in the educational inequalities of Brazilian adult health behaviors between 2013 and 2019. We analyzed data of 49,025 and 65,803 adults (18-59 years of age) from the Brazilian National Health Survey (PNS), 2013 and 2019. Prevalence of health behaviors (smoking, alcohol intake, diet, physical activity and sedentarism) were estimated for three educational strata, for both surveys. Prevalence ratios (PR) between year of survey and between educational strata were estimated by Poisson regression models. Significant reductions were found in the prevalence of smoking, physical inactivity, sedentarism, insufficient consumption of fruits, and the excessive consumption of sweetened beverages. However, an increase was observed in alcohol consumption and binge drinking; vegetable consumption remained stable. Contrasting the favorable change in some behaviors, inequalities among schooling strata remained very high in 2019, specially for smoking (PR = 2.82; 95%CI: 2.49-3.20), passive smoking (PR = 2.88; 95%CI: 2.56-3.23) and physical inactivity (PR = 2.02; 95%CI: 1.92-2.13). There was a significant increase in the educational inequality regarding physical inactivity (21%), insufficient intake of fruit (8%) and in the frequent consumption of sweetened beverages (32%). The persistence and enlargement of inequalities highlight the behaviors and social segments that should be special targets for policies and programs focused in promoting healthy lifestyles.