The original Mahakaleshwar temple is believed to have been built by the Paramara king Bhoja in the 11th century. The temple has undergone several renovations and expansions over the centuries.