Do příběhu Mafie 2 budeme vtaženi ve chvíli, kdy stále probíhá druhá světová válka. Náš hrdina Vito se právě díky zranění vrací na pár měsíců zpět domů, do Empire Bay. Vystupuje z vlaku, na sobě stále oblečenou uniformu, která symbolizuje jeho státní příslušnost. Jak si tak kráčí po nástupišti s vědomím, že na něho nikdo nečeká, najednou spatří svého dávného dobrého přítele Joea Barbara. Není mu sice úplně jasné, jak se dozvěděl o jeho příjezdu (vždyť už se strašně dlouho neviděli), ale je mu to jedno. Alespoň není sám, třeba mu Joe poradí, co dělat dál.
A opravdu – jeho známý ho zavede do nového, nablýskaného auta, kde mu po cestě do baru vypráví o situaci ve státě, o tom, jak je těžké se udržet „nad vodou“, nezapomene se také zmínit o tom, že by pro Vita měl nějakou práci (následně díky svým kontaktům zařídí, že už se Vito do válečné vřavy vracet nemusí). Jelikož náš hrdina momentálně opravdu nemá nic lepšího a ještě k tomu shání nějaký ten dolar k dobru, neváhá a přijímá. V tu chvíli se tedy dostává na dráhu zločinu – nejdříve spolu s Joeam začíná na menších akcích, oba se ale snaží, proklestit si cestu na vrchol – do opravdové mafie…