Math literacy, or lack thereof, is a major issue in our society. Research on mathematics proficiency has begun to support a more conceptual approach to mathematics understanding. Based on this thinking a growing body of literature supports a relation between executive functions (EF) and mathematics ability in both older and younger children. With the majority of research supporting a relation between mathematics and EF we are lead to the question, can training help improve one or both of these skills? The current study addresses this question in young children by looking at the differential impact of various training programs. Three and 4-year-old typically-developing children (N = 104) were randomly assigned to one of four conditions: EF training, number training, EF + number training or an active control condition and participated in three training sessions as well as pre and post test sessions measuring their EF and math abilities. Results indicated a significant positive effect of training with EF training leading to improvements in EF skills and number training and EF + number training showing improvements in math abilities. Interestingly, the EF training also led to improvements in children’s specific counting abilities and number training resulted in improvements in EF skills. These results provide support for a bidirectional relation between EF and math skills, where training in one area can lead to improvements in the other.