Після того як відступив останній льодовик, з'явилося більше придатних територій для лелек і вид поширився в Європі з півночі Африки і, можливо, Балканського та Іберійського півострів, де він залишався під час зледеніння.

Кілька тисяч років тому, коли більша частина нашого континенту була покрита лісами, лелеки були нечисельними. Вони мешкали на заболочених берегах озер і відкритих затоплюваних луках і торфовищах у заплавах великих річок. Коли луки заростали деревною рослинністю, птахи переміщалися на інші луки або річки. Ситуація змінилася, коли європейці почали розвивати землеробство та вирізати ліси, щоб мати більше площі під пасовища та поля. Вже в античній Греції та Римі лелеки оселялися на сільськогосподарських полях і мешкали на міських будівлях. У Західній Європі великі ліси зникли на початку середніх віків. Зі збільшенням площ сіножатей і пасовищ створених і використовуваних людьми, збільшувалася чисельність білих лелек, котрі швидко освоювали нові території.

Проте настали часи, коли зміни, запроваджені людиною в природі, більше не задовольняли білих лелек. До таких змін відносяться: осушення вологих лук, контроль великих річок, зміна ландшафтів, посилення урбанізації. Останнє гніздо лелек у Великобританії було покинуте вже в 1416 році, коли в Литві та на сході Польщі тільки розпочалося їх розселення. Лелеки перемістилися на схід. Цей процес триває й нині. Голо-вне падіння чисельності популяцій білого лелеки в Західній Європі (від Атлантичного узбережжя Франції до річки Ельби) розпочалося в 19 ст. і набрало обертів у 20 ст. За останні 100 років білі лелеки повністю зникли з півночі Франції, Бельгії, Нідерландів, Данії, заходу й півдня Німеччини. Був час, коли лелек взагалі не було в Швеції та Швейцарії. Нині в Нідерландах мешкає менше ніж 10 гніздових пар виду (в 1958 році там мешкало 56 пар, у 1910 році — близько 500), в Данії — 9 пар (у 1890 році там мешкало 4000). Проте за останнє десятиліття лелеки почали будувати свої гнізда на північному сході Санкт-Петербургу й поблизу Москви та Воронежу.

Лелека в культурі, традиціях та історії

У культурах багатьох країн (Греції, Македонії, Болгарії, мусульманських країн близького Сходу й у Марокко) існувало повір'я, що душі померлих людей оселяються в тілі лелеки. Наприклад, Піфагор (572-497 до н. е.), грецький філософ і математик, вважав, що душі мертвих поетів ховаються в тілі лелек, а історик Плутарх (45-125) писав, що в місті Салоніках чоловіка було засуджено до смертної кари через вбивство лелеки, оскільки побутувало вірування, що птах є частково людиною. В мусульманських країнах і досі популярне повір'я, що лелеки переносять до Мекки душі померлих мусульман, котрі не змогли здійснити паломництва за свого життя. За це мусульмани глибоко поважають лелек, а їх вбивство прирівнюють до вбивства людини.

У Молдові лелеки стали символом виноградарів і виноробів. Тут збереглася легенда про лелеку, який приніс виноград до осадженої фортеці, таким чином заручники змогли підживитися, щоб набратися сил для боротьби з ворогом.

У багатьох європейських країнах вірять, що лелека приносить удачу, достаток у сім'ю, добрий врожай тощо. Назва лелеки голландською мовою походить від старонімецького слова «той, що приносить удачу». Також вважали, що лелека на даху захищає будинок від грому. У давній Німеччині лелека був птахом Тора — бога, який посилає громи. Вважалося також, лелеки можуть відімстити за шкоду, принісши в будинок живу гадюку (що реально, адже вони живляться гадюками) або спричинивши пожежу. З Іншого боку, в середньовічній Європі люди вірили, що лелека захищає будинок від пожеж Аристотель (384-322 до н. е.), видатний древній філософ і природознавець, вважав, що лелеки, які зникають кудись восени, впадають у зимову сплячку. Пізніше вважали, що восени лелеки переносять на собі дрібних птахів до Африки.