This study aims to estimate the number of men who have sex with men (MSM) in Ho Chi Minh City (HCMC) and Nghe An province, Viet Nam, using a novel method of population size estimation, and to assess the feasibility of the method in implementation. An innovative approach to population size estimation grounded on the principles of the multiplier method, and using social app technology and internet-based surveys was undertaken among MSM in two regions of Viet Nam in 2015. Enumeration of active users of popular social apps for MSM in Viet Nam was conducted over 4 weeks. Subsequently, an independent online survey was done using respondent driven sampling. We also conducted interviews with key informants in Nghe An and HCMC on their experience and perceptions of this method and other methods of size estimation. The population of MSM in Nghe An province was estimated to be 1765 [90% CI 1251–3150]. The population of MSM in HCMC was estimated to be 37,238 [90% CI 24,146–81,422]. These estimates correspond to 0.17% of the adult male population in Nghe An province [90% CI 0.12–0.30], and 1.35% of the adult male population in HCMC [90% CI 0.87–2.95]. Our size estimates of the MSM population (1.35% [90% CI 0.87%–2.95%] of the adult male population in HCMC) fall within current standard practice of estimating 1–3% of adult male population in big cities. Our size estimates of the MSM population (0.17% [90% CI 0.12–0.30] of the adult male population in Nghe An province) are lower than the current standard practice of estimating 0.5–1.5% of adult male population in rural provinces. These estimates can provide valuable information for sub-national level HIV prevention program planning and evaluation. Furthermore, we believe that our results help to improve application of this population size estimation method in other regions of Viet Nam.