Хотя официально некрополь основан в 1865 году, но ещё в 1842 году, составляя план города, власти задумывали основание кладбища. Когда на нём только начали проводить первые погребения, называлось оно Новым. Сейчас его площадь больше 18,5 га.
Позже кладбище получило своё нынешнее название от имени купца Михайлова. Его пожертвования на постройку храма Всех Святых – кладбищенской церкви - были самыми значительными. Церковь освятили в 1890 году. Интересна она преимущественно своей удивительной росписью. Выполнялась она под руководством самого Виктора Михайловича Васнецова. Александр Алексеевич Волков был ещё одним крупным жертвователем на строительство церкви. Он тоже похоронен на Михайловском кладбище.
На протяжении полуторавековой истории кладбища хоронили здесь многих выдающихся и знаменитых людей. В ХІХ и начале ХХ веков на могилах установлены были памятники, изучение которых сегодня могло бы принести некоторую информацию о том времени, о его быте и культуре. Но, к сожалению, многие из них уничтожены, а некоторые пришли от времени в совершенную непригодность. Утрачены также могилы некоторых знаменитых горожан того времени.
Через дорогу от Михайловского некрополя в 1807 году существовало лютеранское кладбище, рядом с ним чуть позже возникло еврейское. Но в начале 80-х годов ХХ века эти кладбища уничтожили, разбив на их месте парк. Так были утрачены могилы некоторых выдающихся в своё время горожан.
В годы войны на Михайловском кладбище хоронили военнослужащих, которые умерли в госпиталях. В их память установлена стела, останки перезахоронены на другом мемориале, Широкоречинском, построенном в 1981 году, но здесь продолжают хоронить иногда ветеранов войны.
Существует на Михайловском кладбище и захоронение чешских воинов. После краха советской власти в их память был возведен мемориал. Раньше сделать это было невозможно, так как они поддерживали армию Колчака. Это самое крупное захоронение чехов вне Чешского государства.
Установлен на Михайловском кладбище памятник погибшей группе Дятлова. Девять молодых людей погибли во время турпохода. Обстоятельства гибели не выяснены до сих пор. Семь человек из девяти погибших похоронены здесь в 1959 году.
