સંદર્ભો જણાવે છે કે ૧૨મી સદીના ઉત્તરાર્ધમાં મહાકાળેશ્વર મંદિરનું પુનઃનિર્માણ થયું હશે. ઈ. સ. ૧૨૩૫માં દિલ્હીના શાસક સુલતાન ઈલ્તુતમિશે ઉજ્જૈન સહિત માળવા પ્રદેશ પર આક્રમણ કરીને મહાકાળ મંદિરને ધ્વસ્ત કર્યું.