In light of the imminent threat of a growing HIV epidemic in east and southeast Europe, optimal accessibility of primary and secondary HIV preventative interventions, including HIV testing and sexually transmitted infection (STI) care, are fast becoming public health priorities. We surveyed 2150 high school students in Bosnia and Herzegovina, FYR of Macedonia, Serbia, and Montenegro to examine the uptake of HIV testing and associated predictors. Among sexually active youth ( n = 651), 5.9% had already been tested for HIV. In marginal logistic regression, country of origin, type of high school, knowing a friend or relative with HIV, poor self-assessed health status, suspicion of having had an STI, and not having used a condom at first sex were independently associated with HIV testing. Fear of the diagnosis, fear of violation of confidentiality, and not knowing where to go for HIV testing were reported as barriers to HIV testing. Of sexually active adolescents who thought they might have contracted an STI, only 42% had subsequently visited a doctor or health facility. The main reasons for not doing so were spontaneous disappearance of the complaints, fear of the diagnosis and being ashamed of discussing the problem. In conclusion, the uptake of HIV testing among this population of sexually active, urban high school students was found to be low, although a higher prevalence of HIV testing history was observed among students showing evidence of risky sexual behavior. Practical and psychological factors seem to challenge the accessibility of facilities for HIV testing and STI care.