Malatyalı bir hekim tarafından yaptırıldığı için Hekim Han adıyla da anılmaktadır. Taş Han’da, Hekimhan ilçesinin kuruluşu hakkında bilgi veren kitabeler bulunmaktadır. Selçuklular döneminde yapılan Han’ın giriş kapısı üzerindeki kitabenin sol kenarı Ermenice, ortası Selçuklu sülüsü, sağ kenarı ise Süryanice’dir. Kitabe üzerindeki yazılar birbirini teyit etmektedir. Selçuklu sülüsü ile yazılı olan bölümde Han’ın Hicri 615 (Miladi 1218) yılında, Malatya Valisi olarak vazifelendirilmiş II. Kılıçaslan’ın torunu I. Gıyasettin Keyhüsrev’in oğlu Anadolu Selçuklu Sultanı I. İzzettin Keykavus’un (1210-1219) teşviki ve desteği ile Malatyalı ünlü Doktor Ebu Salim bin Ebu’l Hasan El-Malatî tarafından yaptırıldığı yazmaktadır. Han’da bulunan ikinci kitabe, Alaaddin Keykubat (1219-1237) döneminde yapılan avlulu kısmın inşa kitabesidir. Üçüncü kitabede ise Osmanlı döneminde 1071 Muharreminde, Osmanlı mimarı Hasan Ağa tarafından tamir edildiği yazmaktadır. Batı duvarında Osmanlı dönemi tamiratı sırasında kare kesitli üç payanda yapıldı. Batı ve arka duvarında XVII. yüzyıldaki tamirata ait muntazam kesme taş işçiliği görülürken, orijinal olarak kalan doğu duvarının dış yüzünde ise işlenememiş olan büyük taş bloklar görülmektedir. Tamirat sırasında binanın içindeki ara duvarlar onarıldı, sütunların çoğu yeniden yapılmıştır.

Han, Sultan hanları karakterinde olan yapıdır. Çevresinde sivri tonozları olan derin eyvanlar dizili kare formunda geniş bir avlu ile avludan geçilen iki sıralı kesme taş sütunlar üzerine oturtulmuş sivri tonozlarla örtülü kapalı mekândan meydana gelmektedir. Avlu, etrafında sıralanmış odaları olan, arka tarafında dikdörtgen şeklinde ve kendi içinde üç bölüme ayrılmış bulunan kapalı hol kısmından mevcuttur. Giriş kapısının sağında ve solunda yer alan köşe odalar da kare planlı ve kendi içlerinde bölümlere ayrılmaktadır. Her bir odada ocak bulunmaktadır. Han’ın ikinci bölümündeki hol, üç nef (mimaride dik ya da paralel olarak bulunan ve birbirlerinden sütun veya paye dizileriyle ayrılmış olan uzunlamasına mekan) olarak ayrılmış, yan duvarlarında çörtenler mevcuttur. Han oldukça sadedir, süsleme bulunmamaktadır. Aydınlatılması arka duvardan neflere açılan yüksek üç mazgal pencere ile sağlanmaktadır. Han, 2006-2009 yıllarında Malatya Vakıflar Bölge Müdürlüğü tarafından restore edilmiştir.