Evidence-based health promotion programmes, including HIV/AIDS prevention and sexuality education programmes, are often transferred to other cultures, priority groups and implementation settings. Challenges in this process include the identification of retaining core elements that relate to the programme’s effectiveness while making changes that enhances acceptance in the new context and for the new priority group. This paper describes the use of a systematic approach to programme adaptation using a case study as an example. Intervention Mapping, a protocol for the development of evidence-based behaviour change interventions, was used to adapt the comprehensive school-based sexuality education programme ‘The World Starts With Me’. The programme was developed for a priority population in Uganda and adapted to a programme for Indonesian secondary school students. The approach helped to systematically address the complexity and challenges of programme adaptation and to find a balance between preservation of essential programme elements (i.e. logic models) that may be crucial to the programme’s effectiveness, including key objectives and theoretical behaviour change methods, and the adaptation of the programme to be acceptable to the new priority group and the programme implementers.