Based on the new archival data, the article deals with the history of the Kizlyar fortress in the XVIII century, analyzes the facts allowing the supposition that as the place for fortress construction chosen by General V.Y. Levashov there was a tract where there used to be an old fortress. There are some versions concerning the first residents of old Kizlyar. The origin of the name “Kizlyar” and various versions and legends are under consideration in the article.