The aim of the present research was to explore the relationship between exercise self-efficacy (ES) and the stages of exercise behavior changes (EBC) in university students and to predict their exercise behavior changes through self-efficacy, the key structure of Bandura’s social cognitive theory. For this purpose, EBC questionnaire (Cardinal, 1997) and ES questionnaire were randomly distributed among 560 students (294 males and 266 females) who majored in fields other than physical education at Ferdowsi University of Mashhad. The content validity of these questionnaires was confirmed by experts and the internal consistency of the ES questionnaire proved to be 0.76 in a pilot study. The data were analyzed by Spearman correlation coefficient, independent t, ANOVA and stepwise regression tests. The results showed a significant relationship between the ES and the EBC (P<0.01). Also, the stages of exercise behavior changes could be predicted through exercise self-efficacy (ES).