Elementary teachers often hold inaccurate beliefs about the Nature of Science (NoS) and have negative attitudes toward science and mathematics. Using a pre-post design, the current study examined beliefs about the NoS, attitudes toward science and mathematics, and beliefs about the teaching of mathematics and science in a large sample study (N = 343) of pre-service teachers receiving a curriculum-wide intervention to improve these factors in comparison with Science, Technology, Engineering, and Mathematics (STEM) and non-STEM majors in other physics courses (N = 6697) who did not receive the intervention, over a 10-year period. Pre-service teachers evidenced initially more negative attitudes about mathematics and science than STEM majors and slightly more positive attitudes than non-STEM majors. Their attitudes toward mathematics and science and beliefs about the NoS were more similar to non-STEM than STEM majors. Pre-service teachers initially evidenced more positive beliefs about the teaching of mathematics and science, and their beliefs even increased slightly over the course of the semester, while these beliefs in other groups remained the same. Beliefs about the NoS and the teaching of mathematics and science were significantly negatively correlated for STEM and non-STEM majors, but were not significantly correlated for pre-service teachers. Beliefs about the NoS and attitudes toward mathematics and science were significantly positively correlated for both pre-service teachers and STEM students pursing the most mathematically demanding STEM majors. Attitudes toward science and mathematics were significantly positively correlated with accurate beliefs about the teaching of mathematics and science for all student groups.