sequences from four different risk groups in Abuja, Nigeria to estimate transmission patterns between men who have sex with men (MSM) and a representative sample of newly enrolled treatment naive HIV clients without clearly recorded HIV acquisition risks. We develop a realistic dynamical infectious disease model which was fitted to time-scaled phylogenies for subtypes G and CRF02_AG using a structured-coalescent approach. We compare the infectious disease model and structured coalescent to commonly used genetic clustering methods. We estimate HIV incidence among MSM of 7.9% (95%CI, 7.0-10.4) per susceptible person-year, and the population attributable fraction of HIV transmissions from MSM to reproductive age females to be 9.1% (95%CI, 3.8-18.6), and from the reproductive age women to MSM as 0.2% (95%CI, 0.06-0.3). Applying these parameter estimates to evaluate a test-and-treat HIV strategy that target MSM reduces the total HIV infections averted by half with a 2.5-fold saving. These results suggest the importance of addressing the HIV treatment needs of MSM in addition to cost-effectiveness of specific scale-up of treatment for MSM in the context of the mixed HIV epidemic observed in Nigeria.