Early problem behaviors are associated with a variety of cognitive deficits: in verbal ability, executive function (EF) and theory of mind (ToM). Previous studies with different age-groups yield contrasting results: for 2-year-olds, ToM skills appear particularly salient (Hughes & Ensor, 2006), but for 4-year-olds EF appears more important (Hughes, White, Sharpen, & Dunn, 2000). To examine this apparent developmental change in the relative salience of cognitive deficits we followed 122 children from Hughes and Ensor's (2006) sample at ages 3 and 4. Tests of ToM, EF and verbal ability were included at each time-point and multi-informant, multi-measure, multi-setting ratings provided aggregate measures of problem behaviors. ToM and verbal ability showed non-specific associations with problem behaviors, but associations between EF and problem behaviors were strong and specific. In addition, age-3 EF mediated relations between age-2 verbal ability and age-4 problem behaviors.