In this article we analyse the determinants of HIV testing among Nigerian couples using Demographic and Health Survey data set (2008). This study is motivated by the fact that although there is a strong willingness from the Nigerian Government to examine new HIV preventions approaches such as Pre-Exposure Prophylaxis for HIV (PrEP) and Treatment as Prevention (TasP) for HIV serodiscordant couples, the implementation of such policies would require the HIV status of each partner in the couple to be known. This is far to be achieved in the Nigerian context since in Nigeria only 6% of couples know their HIV status. In order to identify potential policies that are needed to increase HIV testing uptake, we use a three-level random intercept logistic model to separately explore the determinants of knowing HIV status among female and male partners. The use of the multilevel modelling allows including the unobserved heterogeneity at the village and state level that may affect HIV testing behaviours. Our results indicate that education, wealth, stigma, HIV knowledge and perceived risk are predictors of HIV testing among both partners while routine provider initiated testing appears to be very effective to increase HIV testing among women. The introduction of financial incentives as well as an increase in routine testing and home-based testing may be needed for large scale increase in HIV testing prior to the implementation of new HIV prevention technologies among discordant couples.