Насеље Кала Курејш се појавило у време инвазије Арапа на Дагестан у 7. веку.
Тврђаву су овде подигли представници племена Курејш, у којем је рођен и пророк Мухамед. Тако је и насеље добило назив - тврђава Курејша.
Кала Курејш је постао главни град једне од најснажнијих локалних средњовековних држава познате као Кајтагшко уцмијство (порекло речи „уцмиј“ - титула владара - је непознато).
Насеље се налази у живописном и недоступном месту, на врху планине око које теку пет река. До Кала Курејша се може стићи само једним путем преко стрмих литица.
Ова стратешка позиција је омогућила тврђави да контролише трговачке путеве и да успешно шири ислам. Дербент и Кала Курејш су била два најважнија центра ислама у Дагестану и на Северном Кавказу.
Овде се данас могу видети рушевине тврђаве и џамије из 11. века, маузолеј последњим владарима (уцмијима) и старо гробље.
Поред насеља стоји и каравансарај из 15. века, нимало типичан за овај регион, јер би Дагестанци радије преноћили код рођака или познаника.
На улазу у Кала Курејш ћете наићи на камену хумку у сенци дрвета чије су гране украшене разнобојним шамијама и пантљикама. Према легенди, овде је сахрањена девојка која се жртвовала за свој народ. Само је она, наиме, по цену живота задржала непријатеље док су се мештани молили у џамији.
Последњи становници Кала Курејша су пресељени у Чеченију 1944. Након рата повратника није било. Људи су одлучили да наставе живот у другим дагестанским градовима и селима.
Данас је Кала Курејш, место ходочашћа, део културног наслеђа Дагестана и Русије.