Мама майбутнього письменника була викладачкою російської словесності (вчителювати вона почала іще в 1913 році, коли про окрему українську літературу й мови бути не могло). Вона була начитаною інтелігентною жінкою. Під час вагітності часто гуляла місцями, пов’язаними з перебуванням у Бердичеві відомих письменників: Бальзака, Конрада, Шолом-Алейхема, Рильського. Родинна легенда стверджує, що старий бердичівський акушер, який приймав пологи, почувши перший крик хлопчика, привітав маму словами: «Мадам! У вас, здається, з’явився письменник!».

Все змінилося в 1933-му, коли заарештували батька. Зиновій Нестайко в молодості був січовим стрільцем, вояком Української Галицької армії. Наприкінці 1920-х, під впливом радянської пропаганди, повіривши в успіхи українізації, зважився переїхати із Західної України, яка тоді була «під Польщею», в УСРР. Працював у Проскурові (нині - Хмельницький) на цукровому заводі, пізніше переїхав у Бердичів.

Його звинуватили у шпигунстві на користь імперіалістичних держав, згадавши службу в Австрійській армії в часи Першої світової війни, духовну семінарію, знання п’яти іноземних мов, а також заслуги його батька, отця Діонізія Порфировича Нестайка, греко-католицького декана, який керував парафією в Бучачі. Більше Всеволод батька не бачив – у пам’яті хлопчика лишився тільки смак цукерок, які той дав синові, коли по нього прийшли. Мамі з сином, рятуючись від голоду довелося тікати до Києва, до маминої сестри.

«У дитинстві в мене не було дитинства», — зізнавався пізніше письменник. Через постійні хвороби він не зміг виїхати з Києва, коли почалася війна, тож два окупаційні роки випало пережити в столиці. «Неволя – це найстрашніше, що може бути в світі – коли йдеш ти з мамою по вулиці, тримаєшся, а будь-який фашист може штовхнути твою маму, образити, і ти нічого не можеш вдіяти. У 1941-му році мені було 11 років, і з того часу я став дорослим, напевно», - згадував пізніше Нестайко.

Бачив він і голод, і смерть. Однак навчився дивитися на світ з оптимізмом і гумором. Як розповідав Всеволод Зиновійович, допомагали родинні перекази — саме такими дотепниками, які викрутяться з будь-якої ситуації, були його дідусь по материнській лінії Іван Довганюк та прадід письменника Семен Довганюк.

Свій творчий шлях Всеволод Нестайко починав у дитячому журналі «Барвінок», де друкувався разом з іншими класиками — Юрієм Яновським, Павлом Тичиною, Наталею Забілою, Оксаною Іваненко, Максимом Рильським. У 1956 році побачила світ збірка оповідань письменника під назвою «Шурка і Шурко». А через два роки - казкова повість «У Країні Сонячних Зайчиків».

Книги Всеволода Нестайка перекладені 20-ма мовами світу.

Найвідомішими книгами Всеволода Нестайка стали підліткова трилогія «Тореадори з Васюківки», казкова казки про Країну Сонячних Зайчиків», оповідання «Одиниця з обманом», «П'ятірка з хвостиком», «Загадка старого клоуна», «Чудеса в Гарбузянах» та багато інших. 1979-го року рішенням Міжнародної ради з дитячої та юнацької літератури трилогія «Тореадори з Васюківки» внесена до Особливого Почесного списку Г.-Х. Андерсена як один із найвидатніших творів сучасної дитячої літератури.

Помер Всеволод Нестайко 16 серпня 2014 року. Похований у Києві на Байковому кладовищі. На похорон сотні киян взяли із собою дзеркальця, щоб провести улюбленого письменника сонячними зайчиками.