Дата постройки Девичьей Башни неизвестна. В верхнюю часть башни справа от входа вмонтирована каменная плита с двустрочной куфической надписью: "губбе (купол, свод) Масуда ибн Давуда". Долгое время, исходя из этой надписи, башню датировали XII веком. Но эта плита явно появилась на башне позднее, так как она случайно и неаккуратно вделана в кладку, не над главным входом, а где-то сбоку, на высоте 14 метров от земли. Скорее всего, это надгробная плита, которой во время ремонта заделали окно в башне, или же имя мастера ремонтировавшего сооружение. При осмотре можно заметить, что на этом месте была квадратная ниша или окно. После установки плиты в верхнюю часть ниши был вставлен случайный камень, а зазоры заделаны раствором, который не использовался при строительстве. То, что на месте плиты располагалось окно, косвенно подтверждается и его расположением — ниша располагалась почти на одном уровне с главным окном башни, но на противоположной от него стороне.

Башня строилась в два этапа. Первый предположительно относится к доисламской эре, а надпись принадлежит к более позднему времени, очевидно, XII веку.

Изначально Девичья башня использовалась как крепостная постройка. В XVIII—XIX веках, начиная с 13 июня 1858 года — как маяк. Позднее, с ростом города, огни маяка на башне стали сливаться с ночными огнями города и в 1907 году маяк был перенесён на остров Наргин.

Девичья башня неоднократно реставрировалась. Во время ремонта, проведенного в середине XIX века русским военным ведомством, с вершины башни исчезли машикули (зубцы), служившие для обороны. Последний раз башня реставрировалась в 1960-х годах. В 1964 году Девичья башня стала музеем, а в 2000 году была включена в список объектов Всемирного наследия ЮНЕСКО.