Подобно предыдущей игре, в Vice City Stories имеется режим мультиплеера, в который можно играть через Wi-Fi. Предлагается десяток различных режимов, включающих в себя автомобили, самолёты и водный транспорт. Режимы мультиплеера:
Vice City Survivor — обычный deathmatch режим, в который вы можете играть свободно для всех или по командам.
Street Rage — стандартный режим уличных гонок, с подрежимом под названием „Quadathon“, подобный триатлону, однако с четырьмя типами транспорта: байк, машина, песочный багги и вертолёт.
Taken for a Ride — этот режим напоминает захват флага в других мультиплеерных играх. Вы должны угнать автомобиль вражеской команды и вернуть его на свою базу. Побеждает та команда, которая угонит больше машин за отведённое время.
Protection Racket — режим основан на стиле завоевания. Когда вы начнёте игру, вы будете или в нападении, или в защите. Если вы защищаете, то должны будете предотвратить уничтожение четырёх автомобилей на вашей базе, а если вы атакуете, то должны, наоборот, уничтожить четыре транспортных средства на вражеской базе. Побеждает та команда, которая сделает всё быстрее.
Tanks for the Memories — где-то на карте находится один танк. Команда, которая больше пробудет в танке — побеждает, однако не всё так просто: у оппонентов есть тяжелое вооружение, такое как Rocket Launcher для того, чтобы забрать танк себе.
Grand Theft Auto — простые автомобильные кражи, режим продажи автомобилей. Вы будете должны захватить определённые транспортные средства на улице и отвезти в назначенное место. Чем лучшее состояние привезённой машины, тем больше вы получите денег. Победит тот игрок, который заработает большее количество денег за отведённое время.
Hit List — один из игроков „маркирован“ и его задача оставаться живым как можно дольше. „Маркированный“ не может видеть других игроков на радаре (если они не находятся в определённом диапазоне) и при этом он не может находиться в транспорте в течение определённого периода времени. Убийство „маркированного“ приводит к передаче роли другому игроку. Побеждает тот игрок, который оставался „маркированным“ дольше всех.
Empire Takedown — две команды, каждая со своим зданием или участком. Имеется набор взрывчатых веществ, расположенных где-нибудь на уровне, и задача каждой команды состоит в том, чтобы первой захватить их и взорвать участок противника. Как только вы успешно установите все бомбы, вы будете должны предотвратить обезвреживания бомб другой командой за определённое время. Когда таймер достигнет нуля, здание взорвётся и будет объявлен победитель.
Might of the Hunter — очень похож на режим „Tanks for the Memories“, но задача — набрать больше всего убийств, и вместо танка имеется Hunter (армейский вертолёт). Игроки также будут вооружены тяжелым оружием.
V.I.P. R.I.P. — две команды, защищающие и нападающие, и один VIP игрок в команде защиты. VIP должен собрать по одному 5 портфелей (когда он собирает один, где-то появляется второй) и затем принести их к пункту отступления. В то время, как это всё происходит, команда нападающих должна пытаться убить VIP. Если VIP убежит, тогда побеждает команда защиты, но если VIP погибнет — победит команда нападающих.