Bitlis'in günümüzde kullanılan isminin nereden kaynaklandığı kesinlikle bilinmemektedir. Bitlis tarih boyunca değişik isimlerle anılmıştır.
Asurlular Bit-Liz, Persler ve Yunanlılar Bad-Lis veya Bad-Lais, Bizanslılar Bal-Lais-on, Babaleison veya Baleş, Araplar Bad-Lis, Ermeniler Pageş veya Pagişi olarak kullanmışlardır. Asur dilinde Bit kelimesi yurt, Bet kelimesi kale manasında kullanılmış, Bit-Liz demek Liz'in Yurdu, Bet-Lis demek ise Liz'in Kalesi manasına gelmektir. Bitlis ismiyle ilgili olarak tarihçilerin ittifakla üzerinde durdukları olay şöyledir: M.Ö. 336 yılında Makedonya kralı II. Filibe ölmüş, yerine Büyük İskender kral olarak geçmiştir. (Şerefname'de Makedonyalı büyük İskender'in, peygamber olarak bilinen İskender Zülkarneyn olduğunu iddia etmektedir. Zülkarneyn 'iki boynuz' manasına geldiğinden, Zülkarneyn'in sürekli doğuya hareket ettiği ve 31 yaşında öldüğünden dolayı büyük İskender olduğunu savunmaktadır. Büyük İskender'in de anlında boynuz halinde iki et yumrusu çıktığı, doğuya seferler yaptığı ve 30 yaşlarında öldüğünden dolayı aynı kişiler olduğunu tezi ileri sürülmüştür.
Ancak bu fikirler bugüne kadar ispat edilememiştir.) Babil'i işgal eden İskender, ordularıyla beraber Hindistan seferine çıkmayı kararlaştırmıştır.3 Bu arada İskender'in anlında boynuza benzeyen iki et parçası çıkmış, maiyetinden gizlemek için sürekli boynuzlu miğfer kullanmak zorunda kalmıştır. Derdine çare için görüştüğü bütün hekimler, şifasının sularda olduğunu ve her gittiği yerdeki suları kullanmasını tavsiye etmişlerdir. Bu nedenle Büyük İskender, uğradığı her yerdeki sularda yüzünü yıkayarak derdine çare aramıştır. Şattülarap'a vardığı zaman Dicle nehrine akan bütün suların araştırılmasını istemiş, bilginleri bu işle görevlendirmiştir. Bütün suları araştıran İskender ve mahiyeti, uzun bir yürüyüşten sonra Bitlis önlerine gelmiştir. Bitlis çayının hastalığına şifa verdiğini görünce Kösür ve Rabat sularının birleştiği yerde karargahını kurmuştur.4 Emrindeki hekimler İskender'e; suyun kaynağına gitmesini istemişlerdir. Bu tavsiye üzerine Bitlis'in doğusundan akan Rabat suyu takip edilerek suyun kaynağına gidilmiştir. Ancak günlerce bu suyu kullanmasına rağmen şifa olmadığını görmüş, bu defa şehrin batısından gelen Kösür çayına yönelmiş, sonunda bu suyun kaynağı olan pınara varılmıştır. Bu pınarın bulunduğu, suların fışkırdığı o dağlık, ağaçlık yeşil tepeler İskender'in gözüne çok güzel görünmüştür. Her taraf zümrüt yeşilliğinde, reyhan ve değişik çiçeklerle bezenmişti. Bu yerin iklimi İskender'i hayran bırakmıştır.
Bu güzel tabiat parçasının havasından ve suyundan faydalanmak için birkaç gün (bir hafta) burada konaklamaya karar vermiştir. Bu suyun kenarında konakladıktan bir hafta sonra, Kösür suyunun derdine şifa olduğu ve boynuzlarının kaybolduğu görülmüştür.1 Günümüzde hala bu suya İskender Çeşmesi denilmektedir. Bu çeşme Bitlis'e 10 km. uzaklıkta, Duav yaylasındadır. Derdine şifa bulan İskender bu yerin ve suyun ebedileştirilmesi için Bedlis (Badlis) veya Leis ismindeki komutanını yanına çağırarak bu çeşmeden 4 saatlik veya 12.000 adımlık uzaklıkta, Rabat ve Kösür sularının birleştiği yerde müstahkem bir kale yapmasını istemiştir. Komutanına (Şerefname'de kölesi olarak geçmektedir) dönerek; 'Ben İran (bazı Kaynaklarda Hindistan) seferinden dönünceye kadar buraya öyle bir kale yap ki, benim gibi bir kral veya kumandan dahi onu ele geçiremesin. Böylece bu kalenin ve yerin ismi kuşaktan kuşağa, yüzyıldan yüzyıla ebedileşsin' demiştir. Bu emri alan Bedlis veya Leis ismindeki komutan hemen işe başlamış, bir yıl gibi kısa bir sürede M.Ö. 331 tarihinde bugün ki kaleyi yapmayı başarmıştır. Hindistan ve İran seferinden dönen İskender şehre geldiği zaman karşısında muazzam bir kale görmüştür. Bedlis'e haber göndererek kaleyi teslim etmesini istemiştir. Kaleyi teslim etmeyeceğini, savaşa hazır olduğu bildirerek İskender'in teklifini reddetmiş ve kale kapılarını kapatmıştır. Bunun üzerine İskender bütün güçleriyle kaleyi kuşatmaya başlamıştır günlerce uğraşmış, kaleyi alamayacağını anlayınca kuşatmayı kaldırarak Rahva ovasına doğru geri çekilmiştir.
İskender'in çekildiği gören Bedlis, Rahva ovasında İskender'in atının ayağına kapanıp bir zarf içinde kalenin anahtarını sunmuş, çıkışı bu yerde olan tünelden kendilerini kaleye davet etmiştir. Kalenin anahtarlarını alan Büyük İskender; 'Bre mel'un, madem ki anahtarı verecektin, niye asi olup bu kadar adamımı kırdırdın' demesi üzerine Bedlis, İskender'den Affını dileyerek; 'Ey büyük fatih! Benim sana karşı başkaldırmam ve direnmem, senin daha önce vermiş olduğun emrin gereği idi. Sen; benim gibi bir kralın alamayacağı bir kale yapmamı emretmiştin. Senin emrin üzerine yaptığım bu kalenin ne kadar sağlam, fethedilmesinin ne kadar imkansız olduğunu ispat etmek amacıyla bu cüreti gösterdim. Şimdi ben ve kuvvetlerim hareketimizden dolayı müstahak göreceğiniz cezaya razı olarak emrinizdeyiz' demiştir.1 Komutanın bu sözlerini çok beğenen İskender, komutanını ödüllendirmek için şehrin yönetimini bu komutanına devrederek ve şehre Bedleis adını vermiştir. O günden sonra şehrin ismi Bedlis kalmıştır. Zamanla bazı harf değişikliklerine uğrayan bu isim, günümüzde BİTLİS adını almıştır.
