Више од шест векова се развијао Лесковац као градско насеље на обалама Ветернице и израстао је у значајан административни, привредни и културни центар. Почетком XIX века у лесковачком крају постојале су бројне школе манастирског типа, а модеран начин школовања је започео доласком учитеља Јосифа Костића. Тако је од познате Ча Митине школе и школске зграде код цркве, образовање деце у лесковачком крају било већ увелико развијено. Зато је и разумљиво да су Лесковчани одмах после ослобођења од Турака, децембра 1878. године желели да у свом граду имају поред мушке и женску основну школу и школе за више образовање своје деце.
Идеју за оснивање гимназије у Лесковцу дао је начелник Министарства просвете Милан Милићевић, августа 1878. године. Почетком марта 1879. године, лесковачка општина је упутила молбу Министарству за отварање гимназије, прихватајући обавезу да је сама издржава. Након тога министар је поднео предлог кнезу, а указ о отварању гимназије је потписан 14. јула 1879. године.
Први наставник кога је министар просвете именовао за предавача је Миленко Ранчић, учитељ тополски, који је у Лесковац дошао септембра 1879. године и успешно организовао пријемни испит.
У току свог рада гимназија је више пута мењала зграду у којој се одвијала настава. У првој школској години се настава обављала у згради бившег лесковачког кајмакама Хафиза Пашагића, која је била једна од најлепших зграда у граду. Касније је школа смештена у другу турску кућу која се налазила близу данашње школе „Светозар Марковић“. Та кућа је носила назив „Кућа Пашагинче“. После рата и дужих припрема, зидање нове школске зграде започело је септембра 1891. године, на месту где је некада био Шашит-пашин конак који је порушен, а био је на простору данашњег сајмишта. Зграда је довршена 1894. године, а усељење је обављено 1895. године. То је била прва и једина зграда подигнута у XIX веку у југоисточној Србији и била је једна од најлепших новоподигнутих модерних зграда у ослобођеним крајевима пре почетка XX века. Нажалост, ова зграда је порушена у бомбардовању Лесковца 6.септембра 1944. године.
После ослобођења Лесковца, октобра 1944. године, гимназија је наставила са радом у женској занатској школи. По завршетку првог полугодишта, школа наставља рад у данашњој згради.
Како је школа временом мењала зграде, тако је мењала и називе. Од оснивања 1879. године, па до 1960. школа је носила назив Нижа реална гимназија, од 1961. до 1979. се звала Гимназија „Станимир Вељковић Зеле“, од 1980. до 1989. године је носила назив Образовни центар „Станимир Вељковић Зеле“ и тада је радила по систему усмереног образовања, од 1989. до 2003. се поново звала Гимназија „Станимир Вељковић Зеле“, а од 2003. године, назив је промењен у Гимназија Лесковац и тај назив школа носи и данас.
Данас школа има 32 одељења и ученици похађају три смера: друштвено-језички, природно-математички и смер за ученике са посебним способностима за рачунарство и информатику.