На початку 60-х років у Павлограді розпочалось будівництво шахт. Місто стало перетворюватися, з’явилася необхідність у потужній інфрастуктурі. В першу чергу на мікрорайоні Шахтобудівників збудували школу, яка стала центром культурно-освітнього простору нового селища. 01 вересня 1965 року почала своє існування середня школа №16 м.Павлограда.

Ця довгоочікувана подія – одна з найвагоміших у літопису селища Шахтобудівників.

Численна дитяча сім’я стала володаркою триповерхової будівлі з приміщеннями для майстерень та великим спортивним майданчиком. 

Візитна картка школи, її обличчя – безперечно, директор. Для директорів, які очолювали шістнадцяту школу, вона стала долею, мрією, життям.

Першим її директором був Куций Анатолій Андрійович, який викладав математику. Директором він пробув неповні шість років. Свою кар'єру продовжив завідувачем міського відділу освіти (був засновником і директором школи №1, викладачем в медичному училищі). Школа була російсько-українською. Багато предметів викладалися українською мовою.

Другий директор - Кулаєв Генадій Семенович, вчитель фізики. В шістнадцятій школі пропрацював 13 років. У школі було по 4-5 паралелей класів, які навчалися в три зміни. При ньому випустився останній український клас в 1974 р.

Третім директором школи був Жура Микола Миколайович, вчитель географії та фізкультури. Пропрацював в школі близько 6 років, після чого став першим директором школи №15 і брав участь в її будівництві.

Четвертим директором стала Котенко Ольга Петрівна, вчитель історії та права. У школі пропрацювала директором майже 10 років. Вона продовжила ремонт, який почав Жура М.М., закупила нові меблі в усі кабінети, найняла художника - Валіахметова А., який розписав стіни на 1-3 поверхах і фойє.

З 2000 року цю естафету перейняла Зла Лідія Степанівна, відмінник освіти України, нагороджена Почесними грамотами Міністерства освіти і науки України, Департаменту освіти і науки Дніпропетровської обласної державної адміністрації, нагрудним знаком «Василь Сухомлинський». Вона пропрацювала директором шістнадцятої школи 21 рік.

15.03.2005р. відповідно Рішення Павлоградської міської ради середня школа №16 м.Павлограда перейменована на Павлоградську загальноосвітню школу І-ІІІ ступенів №16 Павлоградської міської ради Дніпропетровської області.

Серед випускників шістнадцятої школи:

- Бистрик Олена Петрівна - колишній заступник начальника відділу освіти Павлоградської міської ради; 

- Гудожник Леонід - депутат обласної ради, голова КСП "МЮД", меценат; 

- Кожина Ольга В'ячеславівна - лікар-травматолог; 

- Шмідт Олександр Сергійович - лікар; 

- Радіонова Ольга Анатоліївна - заступник начальника податкової інспекції; 

- Радіонов Олександр Миколайович – заступник міського голови;

- Гуржій Олександр Михайлович - адміністратор та провідний актор театру ім.Б.Захави;

- Столярова Наталія Іванівна – директор БТІ.

Кількість учнів на мікрорайоні Шахтобудівників поступово зростала і Павлоградська міська рада виділила кошти на будівництво нової школи. З 15 січня 1990 року почала свою роботу Павлоградська загальноосвітня школа І-ІІІ ступенів №15.

Перший її директор - Жура Микола Миколайович брав участь у будівництві школи та очолив колектив у більш ніж 70 педпрацівників. На той час у школі налічувалось 1200 учнів, які навчалися у дві зміни. 

З 1996р. директором школи була Бистрик Олена Петрівна, вчитель математики. Вона пропрацювала до 2001 року, а потім займала посаду заступника начальника відділу освіти Павлоградської міської ради. 

З 2001 року школа працювала під керівництвом Свєшнікової Людмили Григорівни, а з 2008 року - Таран Лілії Василівни.

У 2021 році дві школи об’єднались в один навчальний заклад під керівництвом Таран Лілії Василівни. 

У 2022 році за рішенням Павлоградської міської ради назву закладу змінено на Ліцей №15 Павлоградської міської ради.

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