The treaty establishing the Economic Community of West African States (ECOWAS) was signed in Lagos on 28 May 1975. Article 27 of the Treaty affirms a long-term objective to establish a community citizenship that could be acquired automatically by all Member States’ nationals. A key objective of the preamble to the treaty is to remove obstacles to the free movement of goods, capital and people in the sub-region. The Phase one of the Protocol on Free Movement of Persons and the Right of Residence and Establishment of May 1979 guaranteeing free entry of Community citizens without visa for ninety days was ratified by Member States in 1980 and put into effect forthwith. Over thirty years after the take off of the Protocol, scholars are united in their submission that the Protocol has failed to fulfill the vision of a borderless sub-region. They point to the ‘ongoing harassment, extortion, inordinate delays and corruption by uniformed personnel at the border areas’, especially of the Nigeria–Benin Republic border as evidence of such failure. Opinions are however, divided on the cause of such failure. While the majority of the commentators are of the view that the protocol has failed as a result of poor implementation occasioned by lack of political will, others reckon that for all its failings, the protocol has performed appreciably well and that all that is needed is added political will on the part of political leaders. It is against this backdrop that the study reexamined the issues resulting to the poor implementation of the ECOWAS Protocol on Free Movement of Persons and Goods in West African Sub- region focusing on Nigeria-Benin Republic borders. Relying on the theory of Neo-functionalism, the study explored the dynamics of trans-border movement between Nigeria and Benin Republic within the context of rising cross border criminal activities and the proliferation of Small Arms and Light Weapons within the sub-region. The study found that the implementation of the protocol has not enhanced cross border movement between Nigeria and Benin, and that the high level of cross border criminal activities and proliferations of arms have gone a long way to undermine the relations between Nigeria and Benin Republic between 1999 and 2012. The study was based on qualitative descriptive technique for its data gathering and analysis. The study then recommends among other policy measures the setting up and intensification of deepening of bilateral relations between Nigeria and Benin through cooperation in scientific and technological matters, development of infrastructures as well as utilization of raw materials for industrial development.