Строительство мавзолея в западной части Казанского Кремля осуществлялось, вероятно, во время правления хана Махмуда (1445-1465 годы).
По его указу было возведено квадратное строение размерами 18х6 метров. Известняковые блоки размерами 40х60х20 сантиметров вырезались по определенным стандартам, их укладывали рядами, скрепляя между собой известковым раствором со слабой примесью кирпичной крошки. Во втором мавзолее, расположенном рядом, был похоронен хан Мухаммед-Эмин в 1518 году. Погребения были совершены по классическому мусульманскому обряду.
Здание мавзолея было разрушено в XVII веке и забыто, но подземные помещения, где хранились останки ханов, были нетронуты. В 1977 году под руководством археолога А.Г. Халикова в ходе раскопок в районе башни Сююмбике были обнаружены и изучены остатки двух монументальных каменных мавзолеев с погребениями. В мавзолеях были расчищены могильные ямы с погребениями в деревянных гробах (250х60-80х50 сантиметров), которые были обложены снаружи тонкой хорошо выделанной кожей, скрепленной при помощи серебряных гвоздей. Эти мавзолеи находились в некрополе знати, располагавшемся в западной части территории ханского двора. Гробницы были богато убраны и хорошо сохранились.
В 2004 году группа археологов во главе с Ф.Ш. Хузиным на глубине трёх метров обнаружила вторую часть мавзолея - три пятиярусные гробницы (мастабы) с четырьмя захоронениями. Позднее было найдено ещё два захоронения. Одно из них располагается под общим склепом и, вероятно, относится к периоду Золотой Орды. Дальнейшие раскопки не проводились, чтобы не повредить найденный белокаменный пол.
В 2005 году мавзолей был музеефицирован, а над двумя хорошо сохранившимися захоронениями для обозрения возведен стеклянный купол. В 2006 году рядом поставлен памятный камень с именами захороненных здесь ханов.