Não se sabe ao certo quando foi construída a primeira fortaleza ou cidadela antecessora da que existe atualmente. Parece certo que foi na Antiguidade[1] e segundo algumas fontes haverá vestígios arqueológicos da existência duma cidadela no local da atual no século IV a.C. A colina com cerca de 20 metros de altura onde se encontra é artificial e foi formada pelas sucessivas reconstruções ao longo dos séculos.[2] Segundo alguns autores, a menção histórica mais antiga, de fontes locais, fala numa fortaleza construída no século VII d.C. pelo Bukhar Khudat (rei) Bidun, que se desmoronou pouco depois e foi reconstruída, seguindo os conselhos de adivinhos, para imitar a forma da "constelação do Grande Urso".[1] Segundo outros, há fontes sassânidas (séculos III a VII) e soguedianas (séculos III a VIII) que atestam a existência da fortaleza no século VII.[3]

Desde essa altura que a cidadela tem a si associadas histórias lendárias. Segundo Maomé ibne Jafar Narshakhi, o historiador de Bucara da primeira metade do século X, a Ark teria sido construída pelo príncipe lendário persa Seoses (Siyâvash),[3] que segundo a lenda está sepultado onde antigamente existia a Porta Kalon, junto à Mesquita Juma (ou Kalyan ou Kalon).[1] No épico persa Šāhnāme ("Épica dos Reis"), de Ferdusi, cerca de meio século depois, o fundador da cidadela é Shiri-Kishvar, um vassalo do grão-cã goturco do final do século VI Kara-Çürin (Tardu).[3] No museu da Ark conserva-se um chicote que teria pertencido ao herói lendário persa Rustã, outro herói do Šāhnāme.[4]

Em 713, Cutaiba ibne Muslim, o governador da província omíada de Coração que conquistou a Transoxiana, mandou construir[3] a primeira mesquita de Bucara, sobre as ruínas dum templo zoroastrista[1] e deu à fortaleza o nome de Kukhendiz.[3] Entre os séculos IX e XII, a cidadela foi reforçada com vários reparos pelos samânidas e pelos caracânidas. O emir samânida Ismail Samani (r. 892–907), que embelezou Bucara, que tornou a sua capital, fez várias adições significativas a cidadela. Arslano Cã (r. 1102–1129) adicionou várias secções, como parte das ambiciosas campanhas de construção empreendidas pelos carcânidas.[3] Os caraquitais e os corásmios destruíram-na e reconstruíram-na três vezes. Em 1220 foi completamente arrasada pelos mongóis,[1] mas no mesmo ano o governador mongol de Bucara Mahmud Yalavach ordenou a reconstrução. O imperador timúrida Ulugue Begue (r. 1447–1449) e o xaibânida Abedalá Cã II (r. 1583–1598) foram responsáveis pela expansão da área da cidadela para três hectares.[3]

A cidadela começou a tomar a forma atual no século XVI, durante o período xaibânida, e praticamente todos os edifícios atualmente existentes são dos séculos XVIII a XX. Foi no século XVI que a cidadela deixou de ser apenas uma fortaleza e residência real para passar a alojar a generalidade dos edifícios governamentais, onde chegaram a residir mais de 3 000 pessoas e se situava, além do palácio real, com salas do trono, de audiências e de receção, o harém, aposentos residenciais e habitações dos escravos, residências de funcionários, casa da moeda, tesouro e outras instalações governamentais, masmorras e uma mesquita.[1] Os cãs jânidas Abdulazize (r. 1645–1680) e Ubaide Alá (r. 1702–1711) levaram a cabo reconstruções radicais. No início houve uma nova reconstrução, quando também foi reforçada a parte ocidental das muralhas.[3]

Em setembro de 1920, quando o Exército Vermelho soviético tomou Bucara e extinguiu definitivamente o Emirado de Bucara, cerca de 80% da Ark foi destruída, devido a um grande fogo, que segundo alguns foi posto pelos soviéticos, segundo outros, por ordem do emir Maomé Alim Cã quando fugiu.[5] O fogo destruiu a totalidade das construções em madeira.[2] Desde então pouco mudou.[3]

A maior parte da cidadela é, desde 1920, um espaço praticamente vazio, com ruínas que aguardam ser escavadas. Os esforços de preservação concentraram-se nas áreas mais visíveis ou públicas, nunca tendo havido uma estratégia de conservação abrangente. As fundações de barro da cidadela apresentam sinais de erosão nos lados norte e ocidental, onde as muralhas se têm vindo a desmoronar.[3]