مَحَجْ قلعة أو مَخَاجْ قلعة أو مَخَاتْشْكَالا، أنشئت في العام 1844م على أساس قلعة عسكرية روسية «بيتروفسكويه». وفي العام 1857 أصبحت مستوطنة وسميت مدينة ميناء «بيتروفسك». وسبب تسميتها بـ «بيتروفسك»، إذ أنه خلال الحملة الفارسية عام 1722 كان في هذا المكان معسكر لقوات البطرس الأكبر.

وفي 15 نوفمبر/ تشرين الثاني سنة 1918، تم تغيير اسمها إلى «شامل قلعة» بقرار من حاكم داغستان آنذاك نوح بيك التاركوفسكي. وذلك للحفاظ على اسم الإمام شامل في ذاكرة الداغستانيين.

وفي 14 مايو/ أيار 1921 بأمر من اللجنة الثورية الداغستانية أصبحت المدينة عاصمة لجمهورية داغستان الاشتراكية السوفياتية وتمت إعادة تسميتها إلى «محج قلعة» تكريماً لمحاج دخدايف، أحد المناضلين من أجل السلطة السوفياتية.

مدينة محج قلعة اليوم هي عاصمة جمهورية داغستان وهي مركز تجاري وسياسي وعلمي وثقافي كبير في جنوب روسيا. وتمتد إلى أكثر من 70 كيلومتراً على الساحل الجنوبي لبحر قزوين ويبلغ عدد نفوسها نحو 550 ألف نسمة يمثلون أكثر من 60 قومية وطائفة دينية. وتبلغ نسبة المسلمين 90 في المئة من مجموع سكان المدينة.