A gengszterfilmek főleg a '30-'40-es években voltak népszerűk igazán, utána a műfajt árnyalta, illetve felváltotta a film noir. Napjainkban lettek felkapva ismét, s ezt az új erőre kapást sokak szerint a The Godfather (itthon: Keresztapa) című Coppola-remekműnek köszönheti a műfaj. A játékipar komolyodásával a XXI. században jött el az idő, hogy a videojátékok világában is megjelenjen a "Keresztapa", melyet ma Mafia néven ismerünk.

A játék (nem is titkoltan) igencsak sokat merít a filmtörténeti remekműből, habár nem egy adaptációról beszélünk. Itt-ott felfedezhetünk enyhe utalásokat, vagy észrevehetünk könnyed karikaturisztikus torzításokat. De kétségtelen, hogy a Mafia alkotói nagyban támaszkodtak a Keresztapára. Mégis az egész olyan egyedinek tűnik, mind történetében, mind a világ kidolgozottságában. A '30-as években, egy fiktív amerikai városban járunk, a beszédes nevű "Lost Heaven"-ben (angolul nem tudóknak: "Elveszett Paradicsom", ha le akarjuk fordítani). A játékos egy taxisofőrt alakít, Tommy Angelo-t, aki a várost járva végzi mindennapi monoton teendőjét. Azonban egy nap a szerencse rákacsint: egy őrült autós üldözés üldözöttjei tesznek neki egy visszautasíthatatlan ajánlatot. A munka elvégeztével kiderül, hogy Paulie és Sam, a két "űzött vad", a város egyik urának, Don Salieri-nek az emberei. Így hamarosan lehetőséget kap rá, hogy csatlakozzon a családhoz, és megjárja a mennyeket - hogy utána kínok közt végül a Pokolba zuhanjon.

A történet abszolút lineáris, a játék ennél fogva erősen sztoriorientált. Csupán 1-2 olyan küldetés van, amit nem szükséges teljesíteni. Ezek Lucas Berone, egy tehetséges autószerelő feladatai, melyek fejében a játékban fellelhető különleges kocsik megszerzésére kapunk lehetőséget. Érdemes ezeket is elvégezni, hiszen amellett, hogy hasznosak, és jó kocsik járnak érte, még rendkívül izgalmasak is!
Persze a lényeg a fő történeti szál, és a játékos valószínűleg soha nem fog lecuppanni róla, minthogy egyértelműen magával ragadó és feszültséggel teli. Ezt elsősorban rendkívül eredeti karaktereinek köszönheti. Paulie, a laza gengszter, Sam, a kissé rejtélyes másik társunk, Salieri, a Don Corleone-hoz hasonló, eleinte nagylelkű gengszter, vagy Ralphie, akit csak úgy jellemeznek a játékban, mint "komplett idiótát" (főként dadogó beszéde miatt). Másodsorban pedig az emeli ki a történetet sok más játékéi közül, hogy felettébb változatos és izgalmas küldetések során bontakozik ki. Lesz itt utcai verekedés, a gengszterfilmekből megszokott őrült üldözések, tolvajlás, bérgyilkosság, sőt, még egy autóversenyen is részt vehetünk.
A különlegesség mindemellett abban rejlik még, hogy minden helyszínre manuálisan nekünk kell elvezetnünk a szabadon bejárható városban. Az útvonalat mi választjuk meg, kivéve, ha időre megy a dolog. Igaz, akkor is nekünk kell vezetni, de, ha nem találjuk meg a legrövidebb utat két pont között, akkor lejár az időnk (persze nem kell félni: általában nagyon sokat adnak ebből a játékban). Persze két küldetés között nem érdemes elbóklászni, ez nem GTA, csak hasonlít hozzá. Illetve ahogy teljesítettük az egyik küldetést, jön utána a másik, tehát nem nekünk kell odacaplatni a helyszínre, és felvenni az adott missziót.

Mindezek mellett még a játék erénye a rendkívüli realizmus. Talán nem is volt előtte, és még kijelenthető, hogy azóta sem nagyon van társa, melyben ilyen szinten odafigyeltek minden apró dolog valósághű megjelenítésére. A város maga grafikailag eleve realisztikus képet ad, még manapság is. A karakterek motion picture technológiával lettek a virtuális térbe varázsolva, így e téren is megdöbbentően valósághű hatást kapunk. Ezek tetejébe még ott van a vezetés és a törvények is. Az autók pontos másai a '30-as évek nagy slágereinek, csupán kissé átnevezve (pl. a Ford T-Model itt Bolt T-Model), vezetésük, fizikájuk pedig szintén megfelel a kornak. Könnyű velük kisodródni, manőverezni kell, a féket megfelelően kell használni, különben nekicsapódunk a másik kocsinak/egyéb akadálynak, illetve ebben a játékban nem fogunk velük szaldózni, mint a GTA-sorozatban (legalábbis nagyobb zuhanás esetén meg is halhatunk, de a kisebb koccanásoknál is sebződünk valamennyit). A törésmodellre sem lehet panasz, mai játékok is megirigyelhetnék. Mindezek tetejébe még a benzinszintre is figyelnünk kell, s ha kiürül a tank, kénytelenek vagyunk egy közeli benzinkúthoz menni, különben leáll a kocsi, és csak nézhetünk, mint a moziban.
Emellett a fejlesztők még a rendőrökre, törvényekre is nagy hangsúlyt fektettek. Különböző kategóriák vannak a bűncselekményekben: 90 km/h-ig (kb. 60 mérföld) még csak bírság, fölötte már "bilincs" jár. Ha pedig elkezdünk lövöldözni, vagy rendőröket gázolni, a rendőrség tüzelni fog ránk. Tehát ebben a játékban, ha áthajtunk a piroson és látja ezt egy "fakabát", akkor meg akar majd bírságolni. Ha összeütközünk valakivel, szintén felkeltjük a rendőr figyelmét.
A harcban szintén figyelnünk kell a fegyverek reakcióit. Pl. a Thompson nagyon erős gépfegyver, de, ha csak úgy lövünk, és nem húzzuk kicsit vissza az egeret, csak össze-vissza szór. Összességében tehát elmondható, hogy szinte minden valóságban is lehetséges szituációban valósághűen reagál a játék.

Zene mi is lehetne más, mint a '30-as évek kiváló jazz számai. Városrészenként különböző dallamok csendülnek fel, szórakoztatóvá téve ezzel az utazást.