Медресе Кукельдаш построено в XVI в., в период господства узбекских правителей Ташкентского удела - Барак-хана и Дервиш-хана. Строителем медресе считается везир ташкентских ханов (1551-1575 гг.), прозванный Кукельдаш («молочный брат хана»). Сохранившаяся вакуфная грамота Дервиш-хана (1569-1570 гг.) завещает в пользу медресе караван-сарай, что свидетельствует о существовании в это время уже готового здания.

Медресе неоднократно приходило в упадок. По свидетельству ташкентского купца Нур-Мухаммеда, рассказ которого был записан в 1795 г. Оренбургской экспедицией, медресе в конце XVIII в. использовалось как караван-сарай. К этому времени, видимо, относится обрушение венчаний башен - гульдаста. Существовавшие до 1800 г. голубые купола над мечетью и дарсханой, а также второй этаж худжр были разобраны на кирпич в 1830-1831 гг. при правителе Ташкента Беклер-беке. Вслед за тем последовал ремонт силами ташкентских мастеров, оставивших свои имена в надписях на майоликовых плитках над входными дверями. Медресе служило кокандским ханам и крепостью (в 1860 г. из него вели пушечный обстрел восставших ташкентцев), и местом казни (до завоевания Туркестана Россией в 1865 г. с парапета на выстланную камнем площадку сбрасывали в мешках уличенных в неверности жен).

В 1868 и 1886 гг., во время сильных ташкентских землетрясений, верх входного пештака разрушился до пят свода. Восстановление свода портала, капитальные исследования и реставрационные работы вели в30-60-е годы XX в. советские реставраторы.

Медресе Кукельдаш - одно из крупнейших сохранившихся медресе XVI в. в Средней Азии. Памятник приподнят на высоком постаменте, выросшем на древних культурных слоях. План его традиционен - прямоугольный двор с худжрами, парадно оформленный передний фасад с высоким порталом, аркатурой и завершающими углы минаретами. Вестибюль имел коленчатые переходы, прямоугольный дворик с большим количеством расположенных в один-два этажа худжр (жилые кельи студентов медресе), входы в которые были оформлены арками.