The city was founded around 385 BC as a Greek colony by Dionysius I of Syracuse by the name of Lissos (Λισσός), as part of a strategy by Dionysius to secure Syracusan trade routes along the Adriatic. Diodorus calls it a polis. The city was separated into sectors by diateichisma (Greek: διατείχισμα, "cross-wall") and there are elements of Syracusan architecture in part of its walls. At a later time it came under Illyrian rule. In 211 BC, Philip V of Macedon captured the citadel of Akrolissos, and Lissos surrendered to him. The town was later recovered by the Illyrians. It was in Lissos that Perseus of Macedon negotiated an alliance against Rome with the Illyrian king Gentius, and it was from Lissos that Gentius organized his army against the Romans. Lissos maintained a large degree of municipal autonomy under both Macedonian and Illyrian rule, as evidenced by the coins minted there. The city was of some importance in the Roman Civil War, being taken by Marc Antony  and then remaining loyal to Caesar. In Roman times, the city was part of the province of Epirus Nova, its name Latinized as Lissus.
From 2004 an excavation started around the ancient Acropolis of Lissos and the Skanderbeg Memorial, which revealed Hellenistic, Roman and Early Byzantine buildings, tombs and other findings.
In Middle Ages Lissus (then known as Alessio) frequently changed masters until the Venetians took possession of it in 1386. It still belonged to them when Skanderbeg died, but In 1478 it fell into the hands of Turks during the siege of Shkodra, with the exception of a short period (1501–1506) when it returned to Venetian domination. Because it was under the Venetian control, it was chosen in 1444 by George Castrioti (Skanderbeg) as a neutral place for the convention of Albanian, Serbian, Dalmatian and other lords of the area aiming at organizing their common defence against the Turks.
Skanderbeg was buried in the cathedral of Lezhë which was dedicated to Saint Nicholas.
Lezhë has also been known by the Italian form of its name, Alessio and in the 19th century as Alise, Lesch, Eschenderari, or Mrtav (Catholic Encyclopedia).
Today Lezhë is a growing city. Its proximity to the port of Shëngjin as well as its location on the national road between the Montenegrin border to the North and Tirana to the South make it an attractive location for industry and business.