Про своє дитинство письменник розповідав: “…Я чомусь згадую самотність. Так уже склалося. Тата свого я не пам’ятаю. Скільки не напружую пам’ять – згадую лише цукерки, якими він мене частував у той вечір, коли прощався з нами… І ще згадую цирк і фокусницю Клео Доротті… Це було в Харкові. Мама повела мене й сестру в цирк, що трохи розрадити після того. як тато поїхав. Згодом виявилося, що поїхав назавжди”. Він загинув у 1933 році в радянському концтаборі.

Рятуючись від голоду, в 1933 році мама – вчителька з двома дітьми переїхала в Київ, де мешкала її сестра, і почала викладати російську мову та літературу в 56-ій школі. Саме з цих років Всеволоду і запам’яталась самотність: хворобливого хлопчика («мабуть, немає такої дитячої хвороби, окрім рахіту, якою б не хворів у дитинстві») мама зачиняла дома, а сама бігла на роботу.

У 1941 р. хлопчик звідав страшні будні війни, окупації, два довгих дитячих роки поневірянь, голоду, страху облав і неволі. Про це він розповідав: «Ми не змогли виїхати, бо я знову захворів. Мамине серце розривалося навпіл. У Москві була моя сестра, що вчилася там, в інституті. Два роки ми нічого про неї не знали. Навчання продовжував у підпільній школі, які організувала мама для дітей. Згадує письменник і націлений у нього чорний отвір дула німецького автомата на Куренівці, де на старому закинутому кладовищі з іншими хлопчиками рвав горіхи. «Жартівливому бистроокому Павлуші куля пробила скроню – він саме повернувся до мене, хотів щось сказати. Тільки вбивши Павлушу, німець побачив, що то хлопець, дитина. І в мене вже не вистрелив. Ніколи було, поспішав…». Після війни, простудіював самостійно дев’ятий клас, склав екстерном екзамени і закінчив школу зі срібною медаллю (була одна четвірка з фізики).

«Я не зогледівся, як несподівано виріс. Витягнувся майже під два метри, і ото дивина — перестав бути рудим. І раптом збагнув, що даремно поспішав вирости, що дитинство — найпрекрасніша, найщасливіша пора людського життя. І так мені захотілося повернутися назад! Назад — у дитинство. Та нема у часу дороги назад. Час іде тільки вперед…»

З 1947 року Всеволод Нестайко навчався на філологічному факультеті Київського університету. У 1952 році закінчив виш, почав працювати в журналі «Барвінок». Пізніше він – редактор видавництва «Молодь», з 1957 року по 1987 рік 30 років! – редактор у видавництві «Веселка». Був дуже вимогливим до себе і до інших. Якщо раптом проскакувала помилка, приходив із київським тортом, схилявся перед редактором і казав: більше ніколи.

Перше оповідання В. Нестайка для дітей побачило світ у 1954 році в журналі «Барвінок». Цього ж року одружився з молодшою на рік філологінею Світланою. Знайшлася у них донечка Ольга – майбутній філолог. Мешкали у Києві на Дружби Народів, згодом на Шовковичній.

Перша збірка «Шурка і Шурко» вийшла 1956 року. Відтоді автор написав чимало цікавих і дотепних книжок для дітей. Розповідаючи про своє бажання стати дитячим письменником, Всеволод Нестайко зазначив: «Всі болі розтоптаного війною мого дитинства викликали жагуче бажання знову повернутися в те дитинство і спробувати пережити його по-іншому, по-новому, не так, як жилося, а так, як мріялося, – сонячно, весело, цікаво, з пригодами не трагічними, а комічними, радісними, щасливими».

Якось Михайло Слабошпицький поцікавився, чому Нестайко над усім сміється, чи немає нічого святого. «А як розібратися, що святе? Хіба наші діти», — почув у відповідь.

У 33 роки в Ірпені при вині та шашликах гусар, який випити любив, але ніколи на чотирьох не ходив, подарував світові найкращий український дитячий роман «Тореадори з Васюківки».

Телефільм, створений за повістю «Тореадори з Васюківки», здобув «Гран-Прі» на Міжнародного кінофестивалі у Мюнхені (1968), на Міжнародному фестивалі в Алегзандрії (Австралія) – головну премію (1969); кінофільм «Одиниця з «обманом» (за однойменною повістю) отримав премію на Всесоюзному кінофестивалі в Києві (1984) і спеціальний приз на Міжнародному фестивалі у Габрово (1985). Всеволод Нестайко написав понад 30 книжок для дітей, виходив накладами 30–50 тисяч примірників, отримував великі гонорари.