Uch sebelum ini dikenali dengan nama Deogarh ("Kubu Tuhan") sehingga abad ke-12.[1] Asal usul nama kini pun masih samar-samar. Dalam satu legenda, Jalaluddin Surkh-Posh Bukhari, Sufi dari Bukhara, tiba di Uch dan telah mengIslamkan anak perempuan pemerintah kota tersebut, Sunandapuri. Semasa pengIslamannya, Jalaluddin Bukhari meminta Sunandapuri untuk membina sebuah kubu yang dinamakan Uch, atau "Tinggi".[1] Menurut legenda yang lain, puteri yang diIslamkan oleh Bukhari merupakan puteri Buddha bernama Ucha Rani, dan nama Uch berasal dari nama puteri tersebut.[3] Selain itu, terdapat juga legenda yang mengatakan Ucha Rani dan Sita Rani, pemerintah Uch dan Sitapur, telah mengahwini Bukhari.[3]

Walau bagaimanapun, pemerintah tempatan Uch telah lama menjadi Islam semasa ketibaan Bukhari pada pertengahan 1200-an. Maka, legenda puteri bukan Islam berkemungkinan hanyalah karya fiksyen.[3]

Nama Uch untuk kawasan itu tidak diiktiraf secara umum untuk beberapa ketika, dan kota itu tidak dirujuk oleh ahli sejarah awal Islam dengan nama Uch.[1] Uch, sebagai contoh, direkodkan sebagai Bhatia yang diceroboh oleh Mahmud of Ghazni pada tahun 1006.[1]