Однажды во время конкурса по бальным танцам в Донецке к Вадиму Елизарову подошла известный педагог София Владимировна Тимофеева. Она сказала, что много слышала про пару Вадима и Нины и хочет познакомиться ближе. Она предложила провести лето в своём родном Севастополе и поработать с её коллективом «Бриз». Вадим Альбертович ни разу до этого не был в Севастополе, хотя всю жизнь мечтал об этом. Приглашение было принято, и Вадим с Ниной приехали в Севастополь в начале лета 1977 года.
Началась активная работа с севастопольским коллективом. Работали три месяца. Новые тренеры привезли много нового материала, очень подробно разбирались в технике танца, предлагали интересные, смелые вариации. Вадим и Нина, конечно, хотели показать себя с лучшей стороны — в их карьере это был первый подобный опыт.
Итогом долгой и кропотливой работы стало проведение конкурса. Организовали его на водной станции Краснознамённого Черноморского флота, рядом с Графской пристанью. Это был конкурс всесоюзного уровня. Приехали пары из России, Молдавии, Украины, даже из Дальнего востока. Было всё: огромное количество зрителей и молодёжи, интерес телевидения и других средств массовой информации. На открытой площадке, рассчитанной на 2000 зрителей, не было ни одного свободного места! Конкурс прошёл блестяще!
Но главное то, как этот конкурс повлиял на дальнейшую судьбу пары Елизаровых.
Секретарю Нахимовского райкома партии Н.Г.Шкариной и генеральному директору Севастопольского морского завода В.И.Подбельцеву настолько пришлось по душе это мероприятие, что они предложили Вадиму и Нине: «А не хотите ли вы поработать у нас, в Севастополе?» Такое предложение стало для пары большой неожиданностью, поскольку у них уже была работа в Саратове. Но от предложения отказываться не стали, и после некоторых раздумий всё-таки решились на судьбоносный шаг, о котором ни разу не пожалели.
По признанию Вадима Альбертовича, когда он создавал свой коллектив, то ещё не осознавал, что создаёт театр. Всего он основал два коллектива: «Эдельвейс» и «Виктория». «Эдельвейс» и сейчас существует на базе Дворца культуры Техстекла в Саратове, а вот «Виктория» позже трансформировалась в понятие «Театр».
Сначала были просто сценические номера. Потом настал период, когда коллектив стали приглашать на торжественные концерты и в гастрольные поездки. Вадим Альбертович всегда переживал по поводу того, что исполнителей бальных танцев зачастую используют как подтанцовку для вокалистов. Он считал бальный танец настолько органичным и совершенным, что его следовало позиционировать как самостоятельный, самодостаточный вид хореографии и искусства.
Первым шоу-номером стала «История любви». В его основе — румба, которую принято называть «танцем любви». Однако Вадим Елизаров не признавал таких стереотипов. Он считал, что каждый бальный танец про любовь, потому что им присуща главная идея — взаимоотношения двух божественных начал — мужчины и женщины.
Большого успеха коллектив добился с программой «Виктория», в основу которой был положен сюжет «Ромео и Джульетты». Впервые коллектив выступил с этой программой в Осло, в Норвегии, в 1999 году и занял четвёртое место. В соревнованиях по формейшн Украина ещё ни разу не добивалась таких результатов. Про коллектив «Виктория» заговорили во всём мире. Но интересно то, что Вадим Елизаров впервые в истории таких соревнований условно поделил команду на Монтекки и Капулетти и наполнил действие сюжетной составляющей. К этому относились по-разному: кто-то категорически не воспринимал, кто-то считал, что это не по правилам... Но уже на следующий год появилось около восьми программ по формейшн с конкретными темами. А главное, что зритель принимал такие нововведения с большим интересом.
В этот период возникло огромное желание трансформировать творческую направленность коллектива. Тогда Вадим Елизаров серьёзно задумался о создании именно театра. Он считал, что танец — это только искусство. Говорить про танец как про спорт — нонсенс. И хотя бальному танцу присущи черты «спортивности», Вадима Альбертовича больше интересовала художественная составляющая Его Величества Танца.
Однажды Вадиму Елизарову позвонили молодые продюсеры из Германии. Они сказали, что хотят сделать шоу, в основу которого будет положена лексика бального танца. Эти люди жили танцами, развивали их творческую сторону. Увидев выступления «Виктории», они еле сдерживались от радости, потому что нашли именно то, что искали. Пришлось серьёзно поработать. Совместное шоу получило название «Фантастика».
Конечно, нужно уточнить, что раньше никто подобного ещё не делал. Вместе с немецкими продюсерами началась разработка структуры концертов на тему «Танец вокруг света». При этом решили показать Англию (формейшн в стиле «The Beatles»), Америку («Нью-Йорк» и рок-н-ролл), Бразилию, Кубу, Испанию, Аргентину... Были задействованы все ритмы, которые лежали в основе бальной хореографии. В Германию «Виктория» приехала за неделю до начала гастролей. Это время полностью посвятили репетициям. Всего же было 50 танцоров и 36 человек обслуживающего персонала. За всё время в Германии состоялось 4 огромных тура, каждый — по 20 с лишним концертов. Именно эта программа стала краеугольным камнем в создании на базе «Виктории» Театра танца.
Отправной точкой считается 17 декабря 1999 года. Именно тогда мэр города Севастополя, глава Севастопольской государственной администрации Леонид Михайлович Жунько издал указ «О создании городского коммунального учреждения — Севастопольский Театр танца» на базе помещения городского Дворца детского и юношеского творчества.
В 2009 году театр удостоили почетного звания «Академический». С 2017 года Севастопольский академический театр танца носит имя своего основателя — Вадима Альбертовича Елизарова.
Сегодня в составе театра танца 50 артистов, среди которых 9 заслуженных артистов Украины, 12 заслуженных артистов Республики Крым и 4 заслуженных артиста города Севастополь. Художественный руководитель - заслуженная артистка Украины Нина Маршева, директор - заслуженный артист Украины Александр Елизаров.