Religious freedom is a key issue linked to the integration of minorities not merely inEurope, but also in the Middle East. This article examines the conduct of Islam with churches in parts of the Middle East in two unique eras; the first era takes us back in time to the offspring of Islam in the 7th century AD, when the Levant and Egypt were under the control of the Roman-Byzantine Empire and Christianity represented the dominant religion, while the second era represents the contemporary period exploring the factual and legal situation on building churches in some Muslim Middle Eastern countries with emphasis on Jordan, being the baptism site of Jesus Christ and having a significant Christian minority.