A considerable amount of evidence supports the value of teaching physical education (PE) and the Common Core in unison. This study investigated mathematics concepts taught during fitness segments in elementary PE. Specifically, we studied student perceptions about linking PE activities and mathematics. We wanted to determine if math concepts could be added to the fitness portion of elementary PE classes without a reduction in the amount of physical activity performed, and if student absorption of mathematics knowledge increased by combining the two fields. Fifty-five upper elementary-age students (8-12 years old) of various ethnic backgrounds from one school in Arizona participated. They wore pedometers and also completed mathematics worksheets preintervention and postintervention. Results showed that 54 of 55 students had extremely positive perceptions, indicating their enjoyment of mathematics as a part of the fitness activity. The students completed the math problems during the fitness segment, with a significant increase in mathematics knowledge. We did not find significant differences between step counts in the regular fitness and mathematics fitness segments. The students enjoyed the mental challenge of mathematics content while being physically active in the fitness segment of the class.