Mineworkers are considered a population at risk for HIV due to risk behaviors associated with migratory work patterns. This was the first study in Mozambique to determine the prevalence of HIV and associated demographic and risk behaviors, and assess use and access to prevention and healthcare services among Mozambicans working in South African mines. Men who had worked in a South African mine in the past 12 months were recruited between February and May 2012 using time location sampling (TLS) at the Ressano Garcia border between Mozambique and South Africa. Demographic and behavioral data were collected through a standardized questionnaire, and HIV prevalence was estimated by testing dried blood spots (DBS) with two enzyme immunoassays. In total, 432 eligible mine workers were recruited. Mean age was 43 years. Most were married or cohabitating; among them, 12.6 % had two or more wives/marital partners in Mozambique. In the 12 months preceding the survey, 24.7 % had an occasional sexual partner, and 6.6 % had at least one partner who was a female sex worker. Only one in five (18.5 %) used a condom during last sex. HIV prevalence among mineworkers was 22.3 %, and 74.6 % of those who tested positive as part of the survey did not know their status. HIV prevalence was significantly higher (p = 0.018) among those that were uncircumcised (31.2 %) than those who were circumcised (18.5 %). Multiple partners (multiple spouses, cross-border relations, and multiple occasional partnerships), inconsistent condom use, and a high proportion of infected mineworkers who do not know their HIV status increases the risk of HIV transmission in this population. Combination strategies involving the promotion of condom use, HIV testing, and male circumcision should be strengthened among mineworkers.