Esiste un mito di fondazione che indica le origini di Khiva in un pozzo fatto scavare dal Sem biblico, mito giustificato dalla notevole antichità della presenza umana nel Khorezm, documentata fin dal V millennio avanti Cristo. Al di là dei miti di fondazione, le origini della città di Khiva andrebbero collocate propriamente attorno al VIII secolo, come fortezza su uno dei rami commerciali della Via della Seta. Tuttavia fu soltanto dopo la frammentazione dell'impero timuride che Khiva assunse importanza in proprio: divenne capitale di un khanato che dalla fine del XVI secolo ne fece la pripria capitale. Khiva divenne famosa per le spaventose condizioni di vita, per la ferocia indiscriminata dei suoi governanti e, soprattutto, per il traffico di schiavi di cui divenne il centro. Una spedizione russa del 1717 fu annientata con l'inganno ma i persiani riuscirono ad occuparla nel 1740 facendone un proprio avamposto. Ricostruita, Khiva continuò sia pure in tono minore a trafficare in schiavi; nell'epoca del big game tra inglesi e russi, furono soprattutto questi ultimi a farne le spese. Soltanto nel 1873 la città venne conquistata dai russi ma il khanato continuò, sia pure formalmente, a sopravvivere fino a dopo la Rivoluzione d'Ottobre.
La Khiva odierna è in buona parte una città-museo frutto di restauri estesi ed accurati, compiuti negli anni Settanta ed Ottanta dello scorso secolo ad opera dei sovietici.