Assessment of the relationship between Islam and public education has been carried out, but the talks remain relevant and interesting to continue to be discussed in the framework of the development potential of society in the era of regional autonomy. This statement is important, because in today's emerging ideas about the relationship and correspondence education with the local communities. Many challenges then facing society in the run the mission in the period of regional autonomy, for example : changes in the orientation of an area for education be more inclined to the materialistic orientation of public education took precedence over religious education, and the fact that the quality of educational services Islam seem inferior education services given by some public schools. And one of the means of Islamic education services, namely through the Madrasah, because as part of the religious education is born from the community will be a dilemma when its existence is not considered. Although many problems related to Islamic education Madrasah- -in this case, but it can be resolved when all parties unite to make a positive contribution for the sake of a common progress. Moreover, the attitude of the government in making discriminatory policy is no longer expected, however, because the madrasah is an integrative part of the national education.