Йшов 1955 рік. Минуло вже 10 років як закінчилася Велика Вітчизняна війна. Відбудовувалися міста і села, відновлювали свою роботу заводи, дитячі садки, школи. Від школи у селі Нововасилівка залишилися тільки стіни. Вона була зруйнована під час війни.Тому школа тимчасово була розміщена в селі Поди в простій селянській хаті. Директором була призначена Яковлєва Олена Кіндратівна. Це була молода, худорлява, висока жінка. Вимоглива. принципова, справедлива і надзвичайно трудолюбива. Вона й очолила усю роботу по відбудові школи.
В 1960 році почалася відбудова школи. Робота велася за рахунок колгоспу імені Ілліча. Допомагали учні, батьки, вчителі. Особливою активністю відзначався голова батьківського комітету Жебров Олександр. На чолі з ним, група батьків звернулася в Центральний Комітет Комуністичної партії України. Надіслали листа з проханням допомогти з обладнанням для електромережі та опалення. Відповідь не забарилася,дуже швидко відшукали потрібні матеріали.
1 жовтня 1961 року переїздили в нову школу без усяких урочистей. Для святкування не було часу, навчальний рік був у розпалі. Під час переїзду у Нововасилівську школу були присутні завідуючий Вільнянським райво Олександр Іванович Середа та секретар Вільнянського райкому Тихонов.
Нововасилівська школа почала діяти. У школі налічувалося більше ста учнів. Молодші класи були класи – комбінати. П’яті - восьмі – окремими класами. Школа була малокомплектна, не було завуча, завгоспа, старшої піонерської вожатої, бібліотекаря. Їхні обов’язки виконували вчителі на громадських засадах.
Педагогічний колектив був дружній і завзятий. Вчителі молоді ( середній вік 30 – 35 років) працьовиті, сумлінні. Ось прізвища вчителів:
- Яковлєва Ольга Кіндратівна - директор школи, вчитель української мови
- Яковлєв Валентин Афанасійович - вчитель фізичного виховання
- Котелевський Володимир Михайлович - вчитель географії біології, хімії
- Демченко Наталія Мефодіївна - вчитель російської мови та літератури
- Білик Федір Дмитрович - вчитель трудового навчання
І в будні, і в свята завжди разом. Тепло своїх сердець вони щиро віддавали учням. Навчали, виховували, готували їх до життя.
Ось уже 50 років цей шкільний дзвоник кличе учнів до школи. Мов журавлята, із свого гнізда, відлітають щороку випускники у велике та складне життя. На їхню зміну приходять інші учні. Школа зустрічає і проводжає своїх дітей.
Керуючись п. 1 рішення 16 сесії Вільнянської районної ради від 18.05.2012 №25 Нововасилівську загальноосвітню школу І-ІІ ступенів Вільнянської районної ради Запорізької області перейменовано в Нововасилівський навчально-виховний комплекс Вільнянської районної ради Запорізької області.
Відповідно до розпорядження Павлівської сільської ради від 10 січня 2018 року НВК перейменовано "Ноовасилівський навчально-виховний комплекс Павлівської сільської ради Вільнянського району Запорізької області"