Kenya is home to one of the worst HIV/AIDS epidemics, with higher prevalence rates in youths in urban slums. We conducted a cross-sectional mixed-methods study in Nairobi informal settlements. The aim was to investigate knowledge, attitudes and behaviours of this marginalized community, and to identify, with a bottom-up approach, the most appropriate interventions to increase the utilization of HIV/STIs services. Preliminary qualitative research was used to draw questionnaires, which assessed: STIs/HIV/AIDS knowledge, attitudes, and behaviours; access and barriers to STIs/HIV/AIDS services; perceived quality of services; the impact of COVID-19. One thousand and fifty-four respondents completed the questionnaire. 48.3% were youth in the community, 23% youth in school, 16.8% young mothers, 6.9% drug users and 5% people attending a technical-vocational training. We found unsatisfactory knowledge of STIs/HIV/AIDS transmission and prevention, and low condom use, mainly due to difficult access, poverty, and gender-based violence. We also found limited use of health services, and lack of trust due to poor attitude of the staff. COVID-19 has widened barriers to access to health services. To reach this population, it is necessary to implement educational interventions, facilitate access to free condoms, and train health centre staff to be more welcoming. Respondents found proximity strategies more efficient, including door-to-door testing and community outreach.