Nigeria is a federal republic with multi-religious, multi-ethnic and multi-legal setting. Shari’ah, the Islamic law, is not merely a legal system, but the way of life for the Muslims who, according to the CIA Factbook, constitute the majority of Nigeria’s population. Besides, Shari’ah was, until its abolition by the colonial imperialists, the official legal system that reigned for about a century in a region that constitutes the largest part of Nigeria, the northern region. For these reasons, Shari’ah was, and is still recognized as a source of the Nigerian legal system with a constitutional authority. This paper examines crucial issues relating to Nigerian Muslims’ constitutional rights with special reference to the challenges hitching the Muslims’ aspiration for Shari’ah implementation in Nigeria. The study is a critical doctrinal research that lays emphasis on the Nigerian Constitution as the primary source. The major findings of the research include the unending challenges faced by the Nigerian Muslims of the non-implementation of Islamic law in its full as it was before the colonial era, non-establishment of a special Court of Appeal for Sharia and the non-recognition of Sharia in its entirety for the Muslims in the judicial structure of southwestern Nigeria. The research suggests that the Muslims have a long way to go for the realization of their dream for a full-fledged Sharia implementation in Nigeria. Therefore, they must rise up for the task in their individual and corporate responsibilities through intellectual, professional and political means available.