Marriage in Islam is a sacred institution. It is a form of ritual submission to Almighty God. For a marriage to be valid, one of the pre-requisites is that it must be entered into in the presence of the female party's guardian (Wali nasab), who must be a blood relative or she must at least have obtained his consent. In the absence of this guardian or without his consent e.g. through deputed power, the marriage is rendered invalid unless it is solemnised by the head of state or his deputy (Wali raja) i.e. the Wali who generally has authority over Muslims in the territory. Nevertheless, there is contention that marriages in need of solemnisation by a Wali raja are prolonged most probably due to procedural difficulties that arise in the process of application for Wali raja or other factors. This paper seeks to examine whether this contention is true and what are the procedural difficulties in obtaining such consent of the Wali raja and what are the ways to overcome those difficulties if any. The research conducted for this paper was basically qualitative, where analysis was based on written procedures and practices outlined by the law. It is hoped that this research will be beneficial to all researchers, academicians, the legal fraternity and the public as a whole.