İlçenin tarihi oldukça eskidir. Yörede ilkçağ ve ortaçağdan kalma birçok eser vardır. Palu ve çevresi Urartu, Roma ve Bizans hakimiyetlerinde kalmış, Halife Hz. Ömer devrinde İslam orduları buraları fethetmiştir (634). Bir müddet sonra Bizanslılar Palu ve Çevresini yeniden alarak Selçuklu akınlarına kadar bölgede varlıklarını sürdürmüşlerdir. Palu yakınlarındaki Şimsat kalesi, o dönemde oldukça önem arz etmiştir.
Selçuklular bu toprakları ele geçirdikten sonra önce Çubukoğullarının daha sonra da Artukoğullarının bölgede hakimiyetleri görülür. Osmanlı Hükümdarı Yavuz Sultan Selim’in komutanlarından Karaçinoğlu Ahmet’in 1515 yılında bölgeyi fethiyle yeni bir dönem başlamıştır.