In no other sector is the challenge of governance much more tasking in contemporary Nigeria than security. Conceived broadly to imply both physical and human security, security has remained at the core of Nigeria’s governance challenges since its return to democracy in 1999. Weak institutions, growing inequality, poverty, injustice and corruption have together undermined the capacity of democracy as a preferred system of rule, to salvage the nation’s security from prolonged years of military rule and inept leadership. With Nigeria’s almost two decades of democratic experience, and the recent ushering to power of another party, the first of this development since 1999, there is indeed, an urgent need for the overhaul of the sector if the expected gains of democracy are to be met. It is the contention of this paper that democracy and security are mutually reinforcing and a disconnect can have deleterious implications for Nigeria. This paper also stresses the need to revamp the country’s security institutions especially in the light of the internal challenges of Boko Haram and in particular, militia groups whose propensity to relapse into military confrontation under the guise of the underlying historical problems associated with the Nigerian state are well documented.