Introduction: Male circumcision (MC) reduces the risk of HIV, and this risk reduction may be modified by socio-cultural factors such as the timing and method (medical and traditional) of circumcision. Understanding regional variations in circumcision practices and their relationship to HIV is crucial and can increase insight into the HIV epidemic in Africa. Methods: We used data from two retrospective HIV surveys conducted in Guinea-Bissau from 1993 to 1996 (1996 cohort) and from 2004 to 2007 (2006 cohort). Multivariate logistical models were used to investigate the relationships between HIV risk and circumcision status, timing, method of circumcision, and socio-demographic factors. Results: MC was protective against HIV infection in both cohorts, with adjusted odds ratios (AORs) of 0.28 (95% CI 0.12-0.66) and 0.30 (95% CI 0.09-0.93), respectively. We observed that post-pubertal (≥13 years) circumcision provided the highest level of HIV risk reduction in both cohorts compared to non-circumcised. However, the difference between pre-pubertal (≤12 years) and post-pubertal (≥13 years) circumcision was not significant in the multivariate analysis. Seventy-six percent (678/888) of circumcised males in the 2006 cohort were circumcised traditionally, and 7.7% of those males were HIV-infected compared to 1.9% of males circumcised medically, with AOR of 2.7 (95% CI 0.91-8.12). Conclusion: MC is highly prevalent in Guinea-Bissau, but ethnic variations in method and timing may affect its protection against HIV. Our findings suggest that sexual risk behaviour and traditional circumcision may increases HIV risk. The relationship between circumcision age, sexual behaviour and HIV status remains unclear and warrants further research.