The HIV/AIDS pandemic is recognized globally as the greatest health challenge of the present generation. It is widely acknowledged to be the foremost killer disease in Africa. Since the first AIDS case was publicly announced in 1986, the astronomical increase in victims has been a matter of concern. The rates of HIV/AIDS infection indicate that Nigeria currently has the third largest rate of HIV/AIDS patients. The UNAIDS (2008) reported that as at 2007, the population of children and adults with HIV/AIDS in Nigeria was 2.6 million. Due to the fact that there is no cure for the virus, HIV/AIDS, counselling is an important aspect of its management. Counsellors in Nigeria have provided pre- and post-test counselling, preventive education seminars, and referrals to other health professionals. However, counsellors' efforts have only yielded limited success because of a number of major challenges. This paper examines some of the challenges involved in meeting the HIV/AIDS counselling needs of Nigerians. Specifically, it addresses challenges faced by government, potential clients, and the Counselling Association of Nigeria, as well as challenges associated with existing cultural practices (indigenous counselling practices). It concludes with specific recommendations for various stakeholders.