Kızıltepe ilçesi kuruluş tarihi milattan önceki yıllara dayanır. Bu tarih, tarihi eserler ve bugün harabe haline gelmiş eski yerleşim merkezlerinde bulunan kalıntılara dayanır. M.S. 1200 yıllarında Artuklular tarafından yapılan ve günümüzde halen ibadete açık olan tarihi camii bu bilgileri doğrulamaktadır.

 Yapılan araştırmalara göre, şehir bir çok kez savaşlar sonucunda harabeye dönüşüp yer değiştirmiştir. Buna göre ilk yerleşim alanı bugünkü şehir merkezinin 10 km güneyinde bir köy yerleşmesi olan Haramhattat'tır. Kızıltepe'nin tarihinde bilinen ilk isimleri Dünaysır ve Telermen'dir. Kızıltepe, Mezopotamya'nın verimli toprakları üzerinde kurulmuş olması, ayrıca Asya ile Avrupa kıtaları arasında önemli bir ticaret yolu olan İpek Yolu'nun kavşağında yer alması nedeniyle tarih boyunca önemli bir yerleşim merkezi olma özelliğini korumuştur. Bu özelliği nedeniyle bir çok savaşlara sahne olmuş ve çeşitli milletler tarafından birçok kez yağmalanmıştır. Artuklular döneminde önemli ticaret ve konaklama merkezi olan Dünaysır, 13. yüzyıl başlarında Eyübiler tarafından yağmalanmıştır. Daha sonra Selçuklu, İlhanlı, Memlük, Karakoyun, Akkoyun, Artuklular ve Timur devletleri yönetimine geçmiştir. Zamanla Dünaysır yerine Telermen, daha sonraları Koçhisar adıyla anılan yerleşim merkezi en son İran'ın hakimiyetindeyken Osmanlı hükümdarı Yavuz Sultan Selim'in İran üzerine düzenlemiş olduğu Doğu Seferi sırasında, Büyük Mehmet Paşa komutasındaki Osmanlı ordusu tarafından ele geçirilmiştir. Bundan sonra Cumhuriyet dönemine kadar Osmanlıların yönetiminde kalmıştır.

 Artuklular döneminde çarşı, hamam, cami ve medreseleri ile önemli ve zengin bir yerleşim birimi olmasına karşın, sürekli savaşlar ve yağmalar nedeniyle Osmanlıların eline yıkıntı durumunda bir köy olarak geçmiştir. Osmanlıların eline geçtikten sonra tekrar onarılan ve canlılığını kazanan yerleşim merkezi, özellikle son dönemlerde İpek Yolu'nun önemini kaybetmesi nedeniyle bu yerleşim alanının önemi giderek azalmıştır. Eski adı Koçhisar olan bu şehrin adı, Cumhuriyet döneminde 1931 yılında Kızıltepe olarak değiştirilerek Mardin'e bağlı bir ilçe merkezi yapılmıştır.