HIV risk in vulnerable groups such as itinerant male street labourers is often examined via a focus on individual determinants. This study provides a test of a modified Information-Motivation-Behavioral Skills (IMB) model to predict condom use behaviour among male street workers in urban Vietnam. In a cross-sectional survey using a social mapping technique, 450 male street labourers from 13 districts of Hanoi, Vietnam were recruited and interviewed. Collected data were first examined for completeness; structural equation modelling was then employed to test the model fit. Condoms were used inconsistently by many of these men, and usage varied in relation to a number of factors. A modified IMB model had a better fit than the original IMB model in predicting condom use behaviour. This modified model accounted for 49% of the variance, versus 10% by the original version. In the modified model, the influence of psychosocial factors was moderately high, whilst the influence of HIV prevention information, motivation and perceived behavioural skills was moderately low, explaining in part the limited level of condom use behaviour. This study provides insights into social factors that should be taken into account in public health planning to promote safer sexual behaviour among Asian male street labourers.