Research on using project work in teaching various disciplines has pointed out a number of challenges facing teachers. Similar research in the EFL classroom, however, has been under-researched. This study aimed to fill the gap with a report on the Vietnamese high school teachers’ challenges in implementing project-based learning in the setting of curricular innovation in English instruction nationwide. The participants of the study were thirty-three EFL teachers from sixteen high schools in both rural and urban areas of the Mekong Delta, Vietnam. With a questionnaire and an in-depth interview, both quantitative and qualitative data were collected. Data analysis indicated that the teachers faced major challenges in time management, adaptation of project activities, student support, and project assessment. These results provide useful implications for how innovative approaches can be successfully implemented, especially with respect to the kind of support EFL teachers need to make project-based learning more feasible in the Vietnamese educational context and similar ones.