A cross-sectional study was conducted among 395 patients presenting with genital ulcers at a primary health care centre in Kigali, Rwanda. Using clinical data and the results of a rapid plasma reagin (RPR) test, we simulated the diagnostic outcome of two simple WHO flowcharts for the management of genital ulcers. These outcomes and a clinical diagnosis were then compared with the laboratory diagnosis based on culture for genital herpes and Haemophilus ducreyi and serology for syphilis. The prevalence of HIV infection was high (73%) but there was no difference between HIV-positive and HIV-negative patients in the clinical presentation and etiology of genital ulcer disease. The proportion of correctly managed chancroid and/or syphilis cases was 99% using a syndromic approach, 82.1% using a hierarchical algorithm including an RPR test, and 38.3% with a clinical diagnosis. In situations where no laboratory support is available, a simple syndromic approach is preferable to the clinical approach for the management of genital ulcer. If an RPR test can be included in the diagnostic strategy, patients with a reactive RPR test should be treated for both syphilis and chancroid infection.