Вскоре Спартак одерживает ряд убедительных побед над римскими войсками, пытавшимися в зародыше подавить восстание рабов и уничтожить его участников. Вершина Везувия и подступы к потухшему вулкану стали ареной кровопролитных боев. Римский историк Саллюстий писал о Спартаке тех дней, что он и его товарищи-гладиаторы были готовы "скорее погибнуть от железа, чем от голода".
Осенью 72 года до н.э. было полностью разгромлено войско претора Публия Вариния, а сам он чуть не попал в плен, что повергло власти Рима в немалое смятение. А перед этим спартаковцы наголову разгромили римский легион под командованием претора Клодия, который самонадеянно поставил свой укрепленный лагерь прямо на единственной тропе, которая вела к вершине Везувия. Тогда гладиаторы сплели из виноградных лоз длинную лестницу и ночью спустились по ней с горного обрыва. Римский легион, внезапно атакованный с тыла, был разбит.
Спартак проявил прекрасные организаторские способности, превратив войско восставших рабов в хорошо организованную армию по образцу римских легионов. Помимо пехоты в спартаковской армии имелась кавалерия, разведчики, посыльные, небольшой обоз, который не обременял войска во время походной жизни. Оружие и доспехи или захватывались у римских войск, или изготовлялись в лагере восставших. Было налажено обучение войск, и тоже по римским образцам. Учителями рабов и итальянской бедноты выступали бывшие гладиаторы и беглые легионеры, прекрасно владевшие различным оружием и боевым построением римских легионов.
Армия восставших рабов отличалась высоким моральным духом и дисциплинированностью. Первоначально командиры всех рангов избирались из числа наиболее опытных и надежных гладиаторов, а затем назначались самим Спартаком. Управление спартаковской армией строилось на демократической основе и состояло из совета военачальников и собрания воинов. Был установлен твердый распорядок лагерной и походной жизни.
О других руководителях мощного восстания рабов в Древнем Риме почти ничего не известно. В истории сохранились только имена Крикса и Эномая, двух, по всей видимости, германцев, которые были избраны восставшими гладиаторами в помощники Спартаку, став военачальниками его армии.
Первые победы восставших рабов нашли широкий отклик. Из Кампании восстание распространилось на южные области Италии — Апулию, Луканию, Бруттию. К началу 72 года до н.э. армия Спартака выросла до 60 тысяч человек, а во время похода на Юг она достигала, по разным данным, численности в 90-120 тысяч человек.
Римский сенат был крайне обеспокоен размахом восстания рабов. Против Спартака были направлены две армии во главе с опытными и прославленными победами полководцами — консулами Г. Лентулом и Л. Геллием. Они надеялись добиться успеха, воспользовавшись начавшимися разногласиями среди восставших. Значительная часть рабов хотела вырваться из Италии через Альпы, чтобы обрести свободу и вернуться на родину. Среди них был и сам Спартак. Однако примкнувшая к рабам итальянская беднота этого не желала.