Отец В. Нестайко во время 1-й мировой войны был «сечевым стрельцом» в австрийской армии, в 1933 году был арестован и погиб в лагерях.
Окончил в 1952 году филологический факультет Киевского государственного университета им. Т. Шевченко. Работал в редакциях журналов «Дніпро», «Барвінок», издательствах «Молодь», «Веселка».
За повесть-сказку «Необыкновенные приключения в лесной школе» Всеволод Нестайко был удостоен в 1982 г. премии им. Леси Украинки. Произведения В.Нестайко переведены на многие языки мира, в том числе на русский, по его повестям и рассказам поставлены фильмы «Единица с обманом», «Чудеса в Гарбузянах», короткометражная лента «Тореадоры из Васюковки».
Его трилогия «Тореадоры из Васюковки» внесена в Почётный список им. Андерсена как одно из наиболее выдающихся произведений мировой литературы для детей.