Background Ukraine has the highest HIV prevalence in Europe, with young people disproportionately represented among populations at high risk. One particularly vulnerable group comprises adolescents who live or work on the streets. This study aimed to measure the extent and distribution of HIV risk behaviours among street-based adolescents in four Ukrainian cities as part of a regional UNICEF HIV prevention programme for most-at-risk adolescents. Methods A cross-sectional behavioural survey was conducted of 805 adolescents (aged 10-19 years) in the cities of Kiev, Donetsk, Dnepropetrovsk and Nikolaev. Using location-based network and convenience sampling, 200 adolescents were reached in each site and were administered a standardised questionnaire on drug use, sexual behaviour, condom use, HIV knowledge, access to prevention services, experience of violence and contact with state institutions and police. Results Considerable levels of HIV risk behaviour were found, including injecting drug use among 15.5% of the sample. Almost three-quarters of adolescents had experienced sexual debut, most before the age of 15 years. Male-to-male sexual behaviour was reported by just under 10% of boys. Condom use was low although varied by partner type. There were high rates of forced sex, and 75.5% of respondents reported police harassment. Conclusions Street-based adolescents in Ukraine are at significant risk of contracting HIV due to involvement in injecting drug use and unprotected sex in personal and commercial exchanges, including male-to-male sex. This group initiates risk behaviours at early ages, and does not appear to have good access to prevention and other health services.