It is important for teacher educators to understand new alternative certification middle and high school teachers' mathematical problem solving abilities and perceptions. Teachers in an alternative certification program in New York were enrolled in a proof-based algebra course. At the beginning and end of a semester participants were given a problem solving examination and were required to reflect upon their students' and their own problem solving abilities. There was a significant improvement in problem solving abilities for the teachers over the course of the semester, and there was a direct correlation between standardized content knowledge test scores and problem solving examination scores. Furthermore, teachers perceived that although their students had improved somewhat in their problem solving over the course of the semester, student problem solving abilities were generally weak due to not understanding how to start a problem, lack of persistence, and poor literacy skills. Teachers perceived that they shared similar problems as their students, but the algebra course and their teaching of problem solving helped them with their own problem solving abilities.