Background. Long-term evaluation studies reveal that high-quality early care and education (ECE) programs that include a lifestyle component predict later adult health outcomes. The purpose of this article is to characterize the nutrition and physical activity (PA) practices, including implementation difficulty and barriers, of licensed center- and family home-based ECE programs serving 2- to 5-year-old children in Minnesota (MN) and Wisconsin (WI). Method. A stratified random sampling procedure was used to select representative cross sections of licensed ECE providers in MN and WI. A total of 2,000 providers (1,000 center-based, 1,000 family home-based) were randomly selected and invited to respond to a 97-item survey with questions representing (1) nutrition and PA practices, (2) barriers to meeting nutrition and PA best practices, and (3) written and implemented nutrition and PA policies. Summated scales were constructed for nutrition-related (range 0-15; Cronbach’s α = .86) and for PA-related best practices (range 0-10; Cronbach’s α = .82). Results. A total of 823 providers returned surveys between August 2010 and March 2011, resulting in a 44% bistate participation rate. Across all programs an average (SD) of 7.0 (4.1) nutrition best practices were already implemented. Center-based providers reported on average 0.8 additional nutrition best practice (7.4 vs. 6.6, p = .01). Across all programs an average (SD) of 5.2 (3.1) PA best practices were already implemented. Center-based providers reported on average one more PA best practice (5.3 vs. 4.3, p < .01). The cost of healthy food and the weather were identified as barriers by 80% of providers, regardless of program type.