Inclusion of incidence data in the surveillance system of HIV is important in order to generate accurate data for effective prevention and control of the pandemic. Retrospective cross-sectional HIV seroprevalence and seroincidence survey was conducted to determine the magnitude of Primary HIV Infection (PHI) and, to identify and describe factors associated with it on stored sera of 455 STIs cases that had been collected and stored during the validation study of syndromic case management algorithms for STIs in Ethiopia, between January - May 2003. Standard HIV-antibody tests were done on all sera and IgG-capture BED-EIA on positive samples for detecting recent infections. Negative Serum samples for HIV antibodies were screened by nucleic acid amplification (HIV RNA PCR) for viral RNA. Incidence was calculated using the consensus formula. OR with 95% CI was used to measure the degree of association between associated factors and PHI and, logistic regression analysis was done to identify predictors of PHI. The overall HIV1/2 seropositivity was found to be 33% and the rate varies among the major STI syndromes, namely, VDS(35%), UDS(20.2%) and GUS(60.5%). Out of the 150 HIV antibody positive cases 15 (prevalence, 3.3%) were recently infected and, annual HIV incidence was estimated to be 11.8% (95% CI, 6.02, 17.58). Acute HIV infection was detected in 7 cases (prevalence, 1.5%) out of 305 HIV antibody negative sera indicating that standard HIV-antibody tests detected only 95.5% of the total HIV infections. The over all prevalence of PHI was 4.8%. Considering both recent and acute infections annual HIV incidence was estimated to be10.1% (95% CI, 5.13 - 14.97). Diagnosis of syphilis was found to be an independent risk factor for PHI for both sexes. Age group 35 – 39 years in males was found to be significantly associated with PHI. The estimated high incidence (10.1%) of HIV-1 infection in this study population indicated that HIV infection is still spreading and targeted intervention is highly recommended. Strong and sustained Provider Initiated HIV Counseling and Testing (PIHCT) with subsequent follow up is recommended for STI patients, particularly those with GUS, during their first appearance at health institutions.