This article examines the introduction and application of Islamic Criminal Law (Sharia Penal Codes) into some states in the northern part of Nigeria by the Governors of those states and the implication of the introduction on Constitutionalism, Rule of Law and Human Rights. The article examines the arguments for and against the application of Sharia Penal Codes put forward by the supporters and opponents of Sharia. The article argues that notwithstanding the provision of section 10 of the 1999 Constitution of Nigeria the enactment of Sharia Penal Codes is within the legislative competence of the states even though these codes contain some provisions which are in direct conflict with some provisions of the Constitution. The article calls for the amendment of the Constitution so as to reflect the multi-religious and multi- national nature of the country in such a way as to confer clear and unambiguous power on any state in Nigeria to promulgate any law to further the rights of the people of the state to fully pursue their religious beliefs provided no religion is imposed on anybody who does not profess it.