Mafia: The City of Lost Heaven
עלילה

המשחק מתחיל בקטע של כ-5 דקות המראה את העיר שבה עלילת המשחק מתרחשת, Lost Heaven, ובסופו נראה תומאס (טום) אנג'לו, הדמות שהשחקן יגלם, נכנסת לבית הקפה ופוגש בנורמן, בלש משטרתי.
הפגישה נערכת בשנת 1938, ובמהלכה מספר טום לנורמן על השנים 1930–1938 שבהן עבד עבור ארגון המאפיה של דון סליארי.
טום מספר על כ-20 משימות ועבודות שעשה במהלך השנים האלו והשחקן יבצע את המשימות שטום יזכיר.
במהלך השנים שבהם עובד טום כמאפיונר, ארגון המאפיה שלו נמצא במלחמה מתמדת עם ארגון המאפיה של דון מורלו, שלבסוף מסתיים בהריגת מורלו על ידי טום.
טום פונה לנורמן מכיוון שסליארי רוצה במותו של טום, טום חושש לחייו ולחיי אשתו שרה (בתו של לויג'י, הברמן בבר של סליארי) ובתו. העלילה מתחילה ב-1930.
טום, נהג מונית עשיר שגר בוילה יוקרתית (הוא פרש מנהג מונית מפני שהרסו לו את המונית והוא נשאר עשיר שגר בוילה מפוארת אבל זה לא מוזכר במהלך המשחק אלא רק ב-free ride extrem) נח על יד המונית שלו בסיום העבודה כאשר סם ופולי באותו הזמן חוזרים ממשימה שמאפיונרים רודפים אחריהם והם מבקשים מטום שיסיע אותם לבר של סליארי.
הם הורגים את המאפיונרים שרודפים אחריהם ונוסעים לבר ואז הם מודים לטום והולכים לבר להגיד לדון סליארי על זה שהוא הציל אותם ושואלים אותו האם אפשר שהוא יצטרף אליהם.
סם יוצא מהבר בלחץ, סם מגיע ומתנצל על זה שהוא בא באיטיות מפחידה ומסביר שרצה לבדוק שאין סכנה באזור, סם אומר לטום שדון סליארי התרגש ושטום יכול להצטרף מתי שהוא רק ירצה, טום עונה לו שמחר הוא יצטרף אליהם וסאם נותן לו כסף לתיקון המונית.
טום מתקן את המונית ונוסע לביתו, למחרת הוא נח במונית שלו ליד הבר של סליארי כאשר שני בריונים מגיעים מחריבים לו את המונית וחוטפים אותו. החוטפים אומרים לטום שהם ילמדו אותו לקח, טום מצליח להדוף אותם, בורח ומגיע לבר של סליארי ומספר על מה שקרה, סליארי הורג את הבריונים ומצרף את טום אל המאפיה שלו ומסביר על הסגן שלו פרנק ועל הכללים ואומר לו שהמשימה הראשונה לו היא להשמיד יחד עם פולי את הרכבים של האויב שלו דון מורלו (פעם דון סליארי ודון מורלו היו חברים טובים אך ב-1920 שהם נסעו לשדה התעופה השתבשה להם עסקה וחברם הטוב ביותר, דון פפון, מת וכולם חוץ מהם נרצחו והם חשדו זה בזה ולכן נפרדו).
פולי מכיר לטום את וינצ'נזו ואת ראלף, ראלף הוא מוסכניק מצחיק ומפגר אך מוצלח, וינצ'נזו הוא חייל מוצלח במיוחד שעובד ביצור נשק ,הם נוסעים לחניון של דון מורלו משמידים את הרכבים הורגים את המאפיונרים ובורחים. יום לאחר מכן הם נוסעים יחד עם סם לעשות עסקת כסף, הם שודדים בנקים ישנים ונוסעים לווילה בקאונטריסייד, כפר על יד שיקגו, פולי וסם נכנסים לתוך הבית, אך העסקה משתבשת כאשר מאפיונרים שגרים בבית חוטפים את סם ומגרשים את פולי ומאיימים על טום, טום נכנס לבית הורג את המאפיונרים ומתחיל לחלץ את סם אך בריון מעיף את טום, טום שולף רובה והורג אותו ואז פורץ לבית שודד ומזהיר אותם לא לקום ומנסה לברוח, טום הורג אותו ומחלץ את פולי וסם.
שנתיים מאוחר יותר ב-1932 טום מתחתן עם שרה הבת של לואיג'י. לואיג'י מבקש ממנו שיוביל אותה בבטחה לביתה, טום עושה זאת, בדרך הם נתקלים בבריונים שיכורים, טום נאבק איתם הורג אותם ומוביל את שרה בבטחה לביתה.
הם שוכבים וטום מכניס את שרה להיריון, למחרת טום מספר לסליארי על המקרה, סליארי מתעצבן ואומר לו שהם ינקמו בהם ושולח אותו ואת פולי להרוג את המאפיה שעשתה זאת, הם הורגים את המאפיה וראשי המאפיה שהם אופנוענים, בורחים פולי וטום רודפים אחריהם והורגים אותם, לאחר מכן טום נוסע למסלול מרוצים וגונב רכב על מנת לחבל בו ובעזרתו של לוקאס ברטוני מחבל ברכב. למחרת פרנק מבקש מטום שישתתף במרוץ מכוניות, הוא משתתף במרוץ וזוכה במקום הראשון וסליארי כמתנה שולח אותו להכיר את לוקאס ברטוני. טום מכיר את לוקאס ומגלה שהוא חבר במשפחה ושהוא אחיו התאום של ראלף, הוא מדריך אותו איך לפרוץ לרכב מפואר, טום גונב את הרכב ולמחרת פרנק מבקש ממנו להסיע אותו למלון ובדרך הוא מבקש מטום שיתחקר את מישל שחושדים שהיא סוכנת ממשלתית, טום מגיע למלון שמנוהל על ידי מאפיה, הורג את כל המאפיונרים ונכנס לחדר של מישל, פוגש את מישל ונזכר בפלאשבק שהיא אחת הנשים שהחמיאו לו על הניצחון במרוץ, טום חוקר את מישל והיא אומרת לו שהיא לא סוכנת ממשלתית ושהיא רוצה לעזור לאח שלה, טום אומר לה שהוא שמח שהיא לא סוכנת ממשלתית ושהוא יספר שהיא לא סוכנת ממשלתית.
מישל נמלטת וטום מפוצץ את המלון. ה-FBI מגלים שהוא פוצץ את המלון ומתחילים לירות לעברו, טום הורג אותם ונכנס לכנסייה שם מתנהלת ההלוויה של בילי וג'וני, המאפיה מגלה שהוא נכנס ותופסת עמדות, טום הורג את כל המאפיונרים, מדבר עם הכומר ומתנצל על זה שהוא הרג את בילי וג'וני, ומסביר שלא הייתה לו ברירה, הכומר סולח לו וטום בורח מהמשטרה לבר תוך כדי שהוא הורג שוטרים ומאבטחים שרודפים אחריו.
שנה לאחר מכן ב-1933 טום ופולי נוסעים לפגוש את סם בכפר של מאפיה ומגלים שהוא נעלם, טום הולך לברר למה, בזמן שפולי שומר בכניסה לכפר טום מגלה שדון מורלו יצר קשר עם המשטרה ושהוא העסיק צבא של שכירי חרב מהמשטרה ,טום הורג את השוטרים והמאפיונרים שתקפו אותו ומספר לפולי על מה שקרה ,פולי אומר שהם יפרצו את האסם שבו הוא נמצא, הם פורצים את האסם, הורגים כל המאפיונרים ומוצאים את סם. לאחר מכן השניים הורגים שוטרים מושחתים שבאו למקום ומחלצים את סם ומגלים שחייליו של דון מורלו מגיעים למקום, טום ופולי בורחים יחד עם סם ותוך כדי כך טום הורג את המאפיונרים שנמצאים בנסיעה חזרה העירה, השניים לוקחים את סם לרופא ונוסעים הביתה .
למחרת סליארי מבקש מטום שיהרוג את פרנק כי הוא בגד בהם ,טום מגלה שפרנק בשדה תעופה, הוא הורג את השוטרים המושחתים שהובילו אותו לשם, לאחר מכן טום מבקש מפרנק שיסביר לו למה הוא בגד בהם ,פרנק מתנצל ומסביר לו שהוא לא התכוון ומסביר שהוא שכח לספר שיש לו נערה בת 14 ואישה בת 46, טום מבטיח שהוא ימצא אותם וכובל את פרנק.
טום מוצא את המשפחה והם שואלים אותו "איפה פרנק?" טום עונה להם שהוא מחכה להם ושהוא יביא אותו, לאחר מכן טום מביא את פרנק,  הוא מביא את המסמכים ופרנק ומישפחתו מהגרים ל ספרינגפילד. טום מזייף את מותו של פרנק ונוסע למסעדה של סליארי, בדרך עובר אצל לוקה ועושה בשבילו משימה שבה הוא הורג בריון שהציק לאח שלו, הוא מספר לסליארי שפרנק מת וסליארי מודה לו על כך.
כעבור 9 שעות סילארי שולח אותו למצוא את סלווטורי שיוביל אותו לדירה של מורלו, טום וסלווטורי פורצים לדירה של סדון מורלו וגונבים משם מסמכים.
כעבור שנה ב-1934 סליארי שולח את טום פולי וסם לעשות הברחת אלכוהול, העסקה משתבשת כאשר המאפיונרים של דון מורלו מגיעים למקום ומתחילים לתקוף, הם הורגים את כולם חוץ מטום סם ופולי, שהורגים את המאפיונרים וחוזרים לבר. לאחר השלמת המשימה עוברת שנה וסליארי וטום הולכים לאכול במסעדה של פאפי שהוא גם חבר טוב של סאלירי אבל אז מגעים חייליו של ג'וניור ומנסים לחסלם וטום וסאלירי הורגים אותם ואת קרלו הנהג של סאלירי שהלשין עליהם אחרי כן טום נשלח להרוג את הקונסילרי של דון מורלו, טום הורג אותו ונמלט יחד עם פולי ,לאחר מכן סליארי אומר לטום שיתנקש בסרג'יו מורלו ג'וניור, סגנו של דון מורלו, אך הניסיונות נכשלים:
בניסיון הראשון הוא מנסה להרוג אות על ידי כך שהוא יגש לטלפון לדבר איתו ופולי יהרוג אותו אבל הניסיון נכשל בגלל שמורלו לא היה שם באותו יום
בניסיון השני (הטמנת פצצה ברכב של ג'וניור) מכיוון שסרג'יו לא היה במקום באותו הזמן ובמקום זאת בחורה נכנסת לרכב, טום מנסה לעצור אותה אך נכשל והיא נהרגת.
בניסיון השלישי הוא נוסע עם פולי להרוג את סארג'יו אך גם זה נכשל בגלל שפולי שכח לבדוק אם יש כדורים במחסנית וגילה לרוע המזל שאין.
בניסיון הרביעי טום ושני אנשים נוספים הולכים לתחנת רכבת שבה ג'וניור יעבור, אך הניסיון נכשל בגלל שסרג'יו מגלה על הניסיון, טום רודף אחריו לנמל שם הוא נלחם במאפיה שלו והורג את כל המאפיונרים, לאחר מכן הוא הורג את סרג'יו מורלו ג'וניור ובורח.
סאם, פולי וטום נוסעים להרוג את דון מורלו, שם הם מגלים שהוא בורח והתחליו במרדף אחריו עד לשדה תעופה, שם הם הורגים אותו ואת שני שומרי ראשו, השלושה חוזרים וחוגגים את הניצחון.
כעבור 3 שנים ב-1938 נשלח טום להרוג את החבר הבחיר במאפיה של מורלו ואחרי שהוא הורג אותו הוא חוזר לבר.
למחרת טום פולי וסם נשלחים להביא סיגריות ובדרך פולי אומר לטום שמחר הם ישדדו בנק, אך בלי לומר לסליארי. טום פולי וסם נוסעים למקום בו נמצאים המסמכים, גונבים אותם הורגים את חיילי האבטחה. הם בורחים וטום נוסע לנמל, גונב את סיגריות ומגיע ליעד.
לאחר מכן טום סם ופולי שורדים התקפה של מאפיה, בהתקפה הם הורגים את כל המאפיה ופולי, טום וסם נוסעים ליעד ומגלים שהסיגריות מזויפות ושזה למעשה יהלומים, הם משמידים אותן ומחליפים אותן באמיתיות ולוקחים לעצמם את היהלומים.
למחרת פולי וטום שודדים בנק מתחת לאפו של סליארי לאחר שהם גילו שהוא צבוע ומנצל אותם בשביל כסף, הם שודדים את הבנק ומתכננים להתחלק בכסף, אך למחרת טום מגלה שפולי נרצח ומקבל טלפון מסם שאומר לו שיפגוש אותו במוזיאון התמונות, שם הם יבררו את מה שקרה אך כשטום מגיע למוזיאון הוא מגלה שסם נשלח כדי להרוג את טום כי סליארי גילה שמאחורי גבו טום ופולי שדדו בנק. טום הורג את כל החיילים של סם ולאחר מכן הוא רודף אחריו ומוצא אותו ויורה בו. סם מספר שמצאו את פרנק ומשפחתו והרגו אותם. טום הורג את סם ובורח.
טום פורש מעולם הפשע וחי עם משפחתו חיים רגילים, מספר למשטרה על סליארי והמשטרה מוצאת אותו ואת ראלף וויצ'נזו וכל האנשים של המאפיה של סליארי והורגת אותם, לואיג'י ולוקאס ברטוני מתגייסים למשטרה.
ב-1951 פוגשים ויטו סקלטה וג'ו ברברו את טום בחצר ביתו והורגים אותו על מנת להשיג את הכסף שהם חייבים לברונו, הם הורגים אותו על ידי כך שהם יורים בו. כאשר שהם נמלטים, טום אומר את מילותיו האחרונות ומת בזמן שבני משפחתו מבכים את מותו.