Всеволод Зіновійович Нестайко народився 30 січня 1930 року в м. Бердичеві на Житомирщині.

Батько, Зиновій Нестайко, під час Першої світової війни був січовим стрільцем в австрійській армії. Його звинуватили у шпигунстві, заарештували й відправили до ГУЛАГу, де він і загинув. Про батька у пам’яті хлопчика лишився тільки смак цукерок, які той дав синові, коли по нього прийшли. Мамі з сином, рятуючись від голоду довелося тікати до Києва, до маминої сестри.

«У дитинстві в мене не було дитинства», — зізнавався пізніше письменник. Бачив він і голод, і смерть. Однак навчився дивитися на світ з оптимізмом і гумором.

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