Service-learning, a major reform in higher education, is considered essential for developing citizenship for the 21st century. This paper reports a study aimed at investigating the problems and challenges faced when implementing service-learning in pre-service education of teachers of English as a Foreign Language (EFL) and carried out in the Sultanate of Oman. The study also investigated the strategies that could possibly be used to overcome the challenges. A two-part questionnaire was designed and administered to a sample of 65 respondents comprising EFL instructors, pre-service student-teachers, administrators and administrative support staff. The first part of the questionnaire included 26 items covering 5 dimensions of challenges and the second consisted of 14 dimensions that covered a total of 77 strategies for overcoming the challenges identified. In general, the challenges were perceived to present serious problems in implementing service-learning; there were no significant differences between respondent groups on account of gender. The study also found that the strategies suggested were perceived to be very helpful in overcoming the challenges with no significant differences between faculty and administrators.