Нина Александровна Винниченко родилась 6 июля 1942 года в Ленинграде. Занималась в танцевальном кружке Выборгского Дома культуры.
Владимир Николаевич Винниченко родился 12 ноября 1937 года в Ленинграде. Его отец Николай Иванович Винниченко (1889-1982) в начале 1920-х годов выступал в составе квартета чечёточников «Фоли», затем, с одним из участников квартета А.Трилингом, а в 1930-е годы танцевал и играл на банджо в теаджазе Л.Утёсова.
Владимир с детства учился степу у отца, вошёл в 1959 году в его номер. После ухода отца на пенсию (1961) стал работать с женой Ниной.
Дуэт был принят в Ленконцерт, где проработал до 1987. Артисты удачно сочетали хорошие внешние данные и умение увлеченно работать, осваивать новые приёмы, расширяя границы жанра.
В первых номерах, поставленных В.Зерновым (танго «Кумпарсита» - 1961), и старшим Винниченко («На прогулке», 1962), молодые танцоры продемонстрировали неплохую технику и элегантность манеры.
Важным этапом явилось сотрудничество с А.Обрантом. Первая совместная работа — «Спортивные ритмы» (музыка Г.Свиридова, 1966) с использованием элементов спорта принесла всем троим лауреатство на Конкурсе концертных номеров. В лирическом «Свадебном танце» (1970) от танцоров уже потребовалось не только актерское мастерство, но и овладение сложным трюком — исполнением степа на лестнице. Последняя работа с Обрантом — «Разговоры» (музыка Ю.Зарицкого, 1974), созданная на русском материале, строилась как ритмический «диалог».
«Визитной карточкой» Нины и Владимира стал номер «В ритмах джаза» (музыка Д.Эллингтона), близкий по стилю «салонным танцам».
Гастроли на Кубе (1977) дали возможность познакомиться с афро-кубинскими и аргентинскими танцами, в результате были созданы: танго «Магабо» и номер на мелодию «Беса ме муча».
Последней значительной работой стал номер, приуроченный к открытию в Москве Всемирной Олимпиады (1980) - «Солнечная серенада».
Уйдя со сцены (1987) выступали с лекциями об эстрадном танце, в 1989 году открыли первую частную школу степа. После смерти Владимира (11.04.1991) Нина Александровна организовала молодёжный ансамбль «Степ-шоу», проявив деловые и педагогические способности. В 1993 году ансамбль завоевал звание дипломанта в первом Московском фестивале «Степ-парад». В 1995 году Ансамбль был преобразован в Санкт-Петербургский театр "СТЭП-ШОУ".