У страшному 1933 р. сім’я Всеволода, рятуючись від голоду, переїхала з Бердичева до Києва, де проживає рідна сестра матері. Тож все своє свідоме життя Всеволод Нестайко прожив у Києві. Мати Всеволода Нестайка працювала вчителькою, їх квартира знаходилась в приміщенні тієї ж школи, де вона вчителювала. З початком німецько-російської війни, а хлопцю було тоді одинадцять років, почалися воєнні труднощі. З матір'ю Всеволод провів два роки в київській окупації. Марія Іванівна організувала в своїй кімнатці підпільне навчання, щоб учні не забули набутих
раніше знань. Ці уроки допомогли – після звільнення Києва, який лежав у руїнах, малого
Нестайка одразу прийняли до шостого класу. Навчаючись у київській школі №63, хлопець
одразу потягнувся до літератури. Тож коли настав час обирати професію, вирішив, що це
буде тільки література.

   У дитинстві разом із сусідом та однолітком Вітасиком Дяченком читали книжки:
Миколи Трублаїні («Лахтак», «Шхуна «Колумб»»), Джека Лондона, Жюля Верна, Бориса
Житкова, та мріяли стати капітанами далекого плавання. Як виявилось, через особливості
зору Нестайко не міг стати моряком, а сусід таки став капітаном.
   В.Нестайко закінчив десятилітню загальну середню школу з однією четвіркою в табелі,
зі срібною медаллю. Через обставини терору та війни не вчився у п’ятому та дев’ятому класах. Курс дев’ятого класу пройшов самостійно за два місяці. Після школи вступив на слов’янське відділення філологічного факультету Київського національного університету імені Тараса Шевченка. Нелегкими були повоєнні роки Всеволода Нестайка: голодними, але то були роки юності і роки студенства, які запам’ятовуються на все життя. Всеволод Нестайко закінчив навчання на філологічному факультеті в 1952 р.

   Працював у редакціях журналів «Дніпро», «Барвінок», видавництвах «Молодь». З 1956 по 1987 р. завідував редакцією у видавництві «Веселка». Одружився, дружина Світлана Пилипівна супроводжувала письменника протягом усього його життя

   П’ятдесятирічний шлях у дитячій літературі засвідчив виданням близько тридцяти книжок оповідань, казок, повістей і п’єс. Перше оповідання для дітей Всеволод Нестайко надрукував у журналі «Барвінок» в 24 роки. Також друкувався у «Піонерії». Перша книжка «Шурка і Шурко» побачила світ у 1956 р. Самими популярними стали твори «Країна Сонячних Зайчиків», «Таємний агент Порча і козак Морозенко. Таємниці ліцею «Кондор», «Пошукове бюро знахідок «Кузя, Зюзя і компанія», «Секрет Васі Кіскіна. Энелолик, Уфа і Страхозаврик»і т.д.