Приміщення школи побудовано в 1934 році в районі ІІ військового містечка. 

Заснована школа була у 1934 році. Для околиць міста стала осередком освіти, тому що навчались у ній діти з Тяжилова, Вінницьких Хуторів, II військового гарнізону. Для дітей військових, що не мали житла у Вінниці, на І поверсі було організовано інтернат, у якому діти перебували цілодобово.

З 1937 року школа існувала як однокомплектна з 8-ма класами для дітей, що проживали в районі школи, Тяжилова, Малих Хуторів, а також для дітей військових службовців ІІ військового містечка та з гарнізонів міст Гайсина, Хмільника.

Розвиток школи

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

 З 1993 р. учні школи І ступеня навчаються в окремому приміщенні – дошкільного виховного закладу №43 (вул. Івана Мазепи, 12).   

Чи часто ми замислювались над тим, яке значення має для нас той куточок земної поверхні, де ми народилися і виросли, де ми навчаємось і працюємо?! Кожна свідома особистість намагається залишити хоч якийсь слід по собі для свого народу та держави.
Останнім часом люди почали частіше звертатись до історії, щоб краще вивчити та пізнати своє минуле. Як легко сучасникам, гортаючи сторінки історії, оцінювати, критикувати, дивуватися з тих чи інших подій та явищ, які мали місце в минулому нашого народу. Але як важко було людям, що були безпосередніми учасниками і свідками цих подій, виживати заради того, щоб через роки їхні онуки та правнуки знали і шанували свою історію.
А чи замислювались ми над тим, що, можливо, усе, що нас оточує, має свою давню, таку несхожу на інші історію?
Вінниця - рідний край. Край близький і дорогий кожному. Із покоління в покоління, як найбільшу коштовність, як зброю і плуг, хліб і вогонь, передають історію краю, рідного міста, школи. І кожен, хто до неї торкнеться серцем, пройметься ще більшою любов'ю до свого краю.
Тече й тече в глибину століть загадкова дорога історії. І кожна її ниточка пов'язана зі стінами рідної школи. І спільне, що об'єднує нас сьогодні, - це слово «школа». Адже немає такої людини, у якої б не тьохнуло серце, згадавши про школу.
Наше місто славиться величчю архітектурних споруд, різноманітністю будинків та пам'ятників, що з давніх-давен є не тільки культурними пам'ятниками, а й мають певне значення у житті кожного жителя.

Школа № 13 поповнює ту плеяду архітектурних пам'яток, яких не знищив час та людське втручання. Школа не одразу стала такою, як нині. Для цього потрібні були роки й роки. 

Спочатку вона була російськомовною школою № 19, а з 1946 року стала школою № 13 з українською мовою викладання.
Нелегкі часи переживала школа у воєнні роки: німецькі загарбники жорстоко розправлялися з наукою: на І поверсі влаштували стайню. Зруйнували стіни, підлогу. Школа залишилась у неохайному, занедбаному стані. Самі склепіння наводили жах на перехожих від того стану будівлі. її відбудова розпочалась зразу із звільненням території від німецько-фашистських загарбників.
Післявоєнна школа була невеличкою: всього 9 класів. На території школи, де зараз ділянки, вчителями і учнями було посаджено фруктовий сад, який і донині радує плодами учнів школи. Були збудовані скляні теплиці, у яких вирощували овочі для шкільної їдальні.    Не обминули учні своєю увагою і тварин, тому у школі було облаштовано живий куточок.
Першим директором школи став Юхим Сергійович Кролівець, учитель, безмежно відданий своїй справі. Він навіть жив на роботі: квартира його сім'ї знаходилась на місці теперішньої бібліотеки. Згодом директор отримав квартиру у вчительському будинку поблизу вулиці Соборної. На долю Юхима Сергійовича випало нелегке завдання: відроджувати школу після війни. За це він був нагороджений орденом В.І.Леніна.
Естафету керівництва Кролівець Ю.С. передав талановитому педагогу, вчителю історії Гордієнку Б.І., що очолив школу з 1959р. по 1985р. Протягом цих років школа займала призові місця у спорті, художніх оглядах (особливо яскравими були танцювальні колективи під керівництвом В.Румянцева).
Рік за роком, переживши не одну реформу, укази, перебудови, настали мирні будні. В зв'язку із збільшенням класів виникла потреба добудувати школу. Отож:, з 1967 року до основного приміщення було добудовано актовий зал, спортивний зал, їдальню, 17 навчальних кабінетів. З того часу школа набула сучасного вигляду.
На честь 60-річчя освіти УРСР у 1982 році токарна майстерня інструментального заводу збудувала приміщення на території школи, де навчались діти початкових класів. Зараз у цьому приміщенні облаштовані 2 кабінети обслуговуючої праці для дівчаток та 2 навчальні майстерні для хлопчиків.
       Однак через певний час знову з'явилася потреба у збільшенні кількості кабінетів. Для цього на території ДНЗ № 43 по вулиці Чехова, 12 було виділено приміщення для навчання дітей молодшого шкільного віку. Зараз там навчається 14 класів початкової школи.
За роки роботи Гордієнка Б.І. школа почала помітно себе проявляти серед освітніх закладів міста.
Однією з кращих піонерських дружин міста була дружина, яка носила ім'я О.Матросова, мала славні традиції: проведення урочистих посвят у жовтенята і піонери біля пам'ятника В.Леніну, проведення параду жовтенятських військ для учнів молодших класів, конкурс пісні і строю для учнів 5-7 класів.
У 1979р. - 1982р. школа брала участь у всесоюзній грі «Зарница», виборола І місце в місті, області. Була учасником республіканської військової спортивної гри «Орленок», керівником якої був О.Ф.Чудовський.
Завдяки таким наставникам, як Мрищук П.В., Богатчук Л.О та інші, школа стала займати призові місця у спорті, була неодноразовим призером багатьох спартакіад, що проводилися міським спорткомітетом серед шкіл міста.
У 1986 році старша піонервожата Артапух Н.В. була рекомендована на Всесоюзний зліт піонерських організацій у Москві.
1986 - 1990рр. школою керував Волосенко І.Д. В цей період особливою гордістю школи був учнівський та учительський хор. Славні традиції хорів започаткував вчитель музики Белін І.І. Разом хор тоді налічував 150 чоловік. Запрошували шкільних митців-аматорів на різні міські урочистості, брали участь у конкурсах, де займали призові місця.
З 1991 по 2001рр. директором школи був В.П. Мрищук. В ці роки школа продовжує займати одне з чільних місць в місті:
• більше 10 років посідала І—II місце у змаганнях «Старти надій». «Перехідний» прапор змагань тривалий час залишався у школі.
• шкільний хор під керівництвом Демішкан Г.Ю і надалі займав І,II місця в оглядах художньої самодіяльності.

З 2001 до 2021 року посаду директора обіймала Лученко Світлана Володимирівна - талановитий і чуйний педагог. За час роботи зарекомендувала себе ініціативним, вдумливим керівником, створила творчий, продуктивний мікроклімат, сформувала команду однодумців. Протягом цих років школа не втрачала темпу розвитку. У спорті й художній самодіяльності колектив традиційно тримав першість серед освітянських закладів міста.
З 2021 року заклад очолює Седельов Олександр Олександрович - досвідчений, креативний, енергійний, демократичний керівник. Учитель-методист, за фахом - учитель географії. Велику увагу приділяє вдосконаленню освітнього процесу, зміцненню матеріально-технічної бази та створенню соціально-активної школи.
З 1 січня 2022 року рішенням Вінницької міської ради №742 від 24.12.2021 року комунальний заклад «Загальноосвітня школа І-ІІІ ступенів №13 Вінницької міської ради» перейменовано на КОМУНАЛЬНИЙ ЗАКЛАД «ВІННИЦЬКИЙ ЛІЦЕЙ №13».