Background: The World Health Organization (WHO) Department of HIV/AIDS led the development of public health guidelines for delivering an evidence-based, essential package of interventions for the prevention and treatment of HIV and other sexually transmitted infections (STIs) among men who have sex with men (MSM) and transgender people in the health sector in low- and middle-income countries. The objective of this paper is to review the methodological challenges faced and solutions applied during the development of the guidelines. Methods. The development of the guidelines followed the WHO guideline development process, which utilizes the GRADE approach. We identified, categorized and labeled the challenges identified in the guidelines development process and described the solutions through an interactive process of in-person and electronic communication. Results: We describe how we dealt with the following challenges: (1) heterogeneous and complex interventions; (2) paucity of trial data; (3) selecting outcomes of interest; (4) using indirect evidence; (5) integrating values and preferences; (6) considering resource use; (7) addressing social and legal barriers; (8) wording of recommendations; and (9) developing global guidelines. Conclusion: We were able to successfully apply the GRADE approach for developing recommendations for public health interventions. Applying the general principles of the approach while carefully considering specific challenges can enhance both the process and the outcome of guideline development. © 2012 Akl et al.; licensee BioMed Central Ltd.