We examined several facets of general pedagogical knowledge and skills of early career mathematics teachers, asking how they are associated with characteristics of teacher education, teaching experience, and working conditions. Declarative general pedagogical knowledge (GPK) was assessed via a paper-and-pencil test, while early career teachers' skills to perceive and interpret classroom situations were assessed via video-vignettes. Data from a follow-up study of TEDS-M Germany in 2012 were used, including a sample of 278 early career middle school teachers of mathematics. While teachers' declarative knowledge can be predicted by teacher education grades, teachers' skill to interpret classroom situations presented by videos can be predicted by their amount of time spent on teaching relative to their overall working time, which is interpreted as a form of deliberate practice. Different competence profiles of pedagogical knowledge and skills are identified via latent-class analysis. Besides teaching experience, profiles are associated with generic teaching challenges (motivating students, disruptive student behaviour) perceived by the teachers. Implications of findings for professional development of early career teachers are discussed.