Workplace health promotion programs should be tailored according to individual needs and efficient intervention. This study aimed to determine the effects of nutrition and exercise health behaviors on predicted risk for cardiovascular disease (CVD) when body mass index (BMI) is considered. In total, 3350 Taiwanese workers were included in this cross-sectional study. A self-reported questionnaire was used to measure their nutrition and exercise behaviors. Data on anthropometric values, biochemical blood determinations, and predicted CVD risk (using the Framingham risk score) were collected. In multiple regression analyses, the nutrition behavior score was independently and negatively associated with CVD risk. Exercise was not significantly associated with the risk. However, the interactive effect of exercise and BMI on CVD risk was evident. When stratified by BMI levels, associations between exercise and CVD risk were statistically significant for ideal weight and overweight subgroups. In conclusion, nutrition behavior plays an important role in predicting the CVD risk. Exercise behavior is also a significant predictor for ideal weight and overweight workers. Notably, for underweight or obese workers, maintaining health-promoting exercise seems insufficient to prevent the CVD. In order to improve workers’ cardiovascular health, more specific health-promoting strategies should be developed to suit the different BMI levels.