Using a large-scale, standardised English language proficiency test (TOEFL® "Primary"™), this study examined Kenyan primary school students' English reading and listening proficiency and explored challenges primary school teachers face in using English as the medium of instruction (EMI) to teach their multilingual students. The test was taken by 4768 students in Standards 3-7 from 51 primary schools across the country in Kenya. Seventeen primary school teachers, representing six major geographical regions, participated in semi-structured interviews to explore their teaching challenges. Results show that, regardless of standard/grade level, the majority of the participating students were beginner-level English language users, which suggests that they may not have the language skills needed to understand classroom instruction and learn the subject matter content effectively in English. Interview findings indicate that, as they implement the EMI policy, teachers encounter five major challenges: (1) mother tongue interference, (2) students' attitudes toward English, (3) lack of usefulness of English language in the community, (4) resource constraints and (5) diverse student backgrounds. The results have pedagogical implications for EMI implementation in similar multilingual contexts.