Higher education is becoming increasingly internationalized, and the use of English as a medium of instruction for academic content has become commonplace in countries where English is not the native language. However, concerns are growing that the trend toward English-medium instruction (EMI) has accelerated without sufficient thought to the challenges of the implementation processes. This article discusses the challenges facing higher education institutions adopting EMI and proposes a typology for understanding them. Drawing on previously unpublished data from a study of universities in Japan, a context in which EMI is rapidly expanding, the article reconceptualizes prior understandings and identifies four categories of challenges: linguistic, cultural, administrative and managerial, and institutional. The categories are dynamic and context dependent, with institutional challenges playing a particularly prominent role in Japan. The proposed typology is offered as a conceptual framework for policy makers and program implementers designing effective implementation strategies for EMI.