По преданию основание города связано с именем Тамерлана (Темир-Хана). В 1396 войско Тамерлана, возвращаясь из похода на Золотую Орду и Русь, стояло лагерем у озера, названного горцами Темир-Хан-Шура, на месте стоянки войска вскоре возник одноимённый аул (озеро осушено в 1854).
Город выгодно расположен у горных проходов во внутренние районы Дагестана и в 1834 близ аула построены русские военные укрепления - крепость Темир-Хан-Шура. Шура кумыкское "озеро", т.е. всё вместе "озеро Тамерлана". Во время Кавказской войны (1817-64) крепость Темир-Хан-Шура в 1843 выдержала полутарамесячную осаду горцев под предводительством имама Шамиля, в 1849 - налёт конников Хаджи-Мурата.
С 1847 - место пребывания управляющего гражданской частью в Прикаспийском крае, в 1860 - центр Дагестанской области. Город с 1866.
В 19 в., особенно после окончания Кавказской войны, город привлекал к себе внимание деятелей культуры. В Темир-Хан-Шуре были поэты и писатели А.И. Полежаев, А.А. Бестужев-Марлинский, художники Ф.Т. Рубо, И.К. Айвазовский, Н.А. Ярошенко, писатель А. Дюма-отец и др.
В ноябре 1920 в Темир-Хан-Шуре провозглашена автономия Дагестана. В 1922 переименован в честь участника борьбы за советскую власть в Дагестане Уллубия Д. Буйнакского (1890-1919).
Буйнакск сильно пострадал во время землетрясения 14 мая 1970.