Background: Identification of recent HIV infections provides a description of the current pattern of HIV transmission and, consequently, can help to design better preventive interventions. Our study shows the first implementation in Spain of the Serologic Testing Algorithm for Recent HIV Seroconversion (STARHS) strategy. We assess the viability of introducing STARHS in our setting and describe the frequency and epidemiological characteristics of recent infections (RIs). Methods: Between 2003 and 2005, HIV-positive blood samples drawn for diagnostic purposes were collected from 28 Spanish laboratories to be tested using STARHS. Samples from patients with a previous HIV diagnosis, age <18 years, <200 CD4 cells/μl or clinical AIDS criteria were excluded from the analysis. Results: A total of 660 (19.2%) samples were classified as Rl. Most people identified with Rl were male (79.8%) with a median age of 33.1 years, and 62.5% occurred among men who have sex with men (MSM). Immigrants made up 26.5% of individuals identified with RIs, with 48.7% coming from South America. Among the individuals with Rl, at least 16.5% had reported another sexually transmitted infection (STI) during the year before the HIV diagnosis. Conclusion: The study shows that the implementation of STARHS in our setting is feasible and has highlighted important features of the local HIV epidemic, such as the ongoing spread of HIV among MSM, the potential role of STIs in RIs and the vulnerability of immigrants as a new target population.