Třetí díl je pokračování série, nikoliv její restart. Příběh, i když velmi nepřímo navazuje na díl druhý a jelikož Mafia II nechala za sebou mnoho otázek bez odpovědí, tvůrci třetí Mafie se toto pokusí napravit. Dozvíme se například, co se stalo s mafií v Empire Bay, proč se Vito rozhodl utéci do New Orleans a spojit síly s místním šéfem italské mafie, donem Marcanem. Vývojáři jsou si vědomi, že spoustu hráčů zajímá osud nejlepšího přítele Vita, Joe Barbary. Nebude to hned první věc, co se dozvíte, ale jak Lincoln bude poznávat Vita a jeho minulost, hráči by se měli dozvědět, co se Joem stalo.