Developing high levels of mathematical skills in students is a concern for teachers worldwide, since most of the fastest growing occupations require significant mathematics or science preparation. Teachers need to be prepared to teach mathematics successfully. If teachers are not fluent in simple mathematical calculations, they may not feel confident in applying complex pedagogical content knowledge. This paper explores the association between mathematics fact fluency and mathematics teaching self-efficacy. Fifty-seven elementary teacher candidates completed two assessments. The first assessment was a mathematics fact fluency assessment evaluating the participants' fact fluency for the four basic mathematics operations: addition, subtraction, multiplication, and division. The second assessment was the commonly used Mathematics Teaching Efficacy Beliefs Instrument. Pearson r correlations were completed to examine the relationship between mathematics fact fluency and self-efficacy in teaching elementary mathematics. Positive relationships were found between participants' scores on the Mathematics Teaching Efficacy Beliefs Instrument and the addition and multiplication fact fluency scores. Personal mathematics teaching efficacy was related to addition fact fluency with higher teacher candidates' efficacy scores associated with the correct completion of more addition facts. Mathematics teaching outcome expectancy was positively related to addition, multiplication, and total facts completed.