Basing on a comparative linguistic and historical analysis of the famous Avar ballad about brave bandit Khochbar – burned alive by perfidious prince of Khunzakh, the author examines changing relations between power and violence as well as cultural memory of banditry in pre-modern Highland Daghestan. After the establishment of the Russian colonial administration by the mid-19th century traditional male unions of Muslim mountaineers became outlaws and gradually disappeared, their military chieftains having turned into criminals. In people's cultural memory this shift is reflected in the new image of a noble bandit like a Muslim Robin Hood. The paper also includes a new Russian translation of the song of Khochbar together with its Avar text and detailed ethnographic comments.