Сюжет "Mafia: The City of Lost Heaven" розбитий на двадцять розділів (деякі поділені на дві частини) за принципом опису подій, що відбуваються в один день. Під час глави головний герой виконує кілька місій.
Усі три частини Mafia відрізняються між собою радикально, нехай їхній сюжет частково пов'язаний. В основі кожної лежить сильна історія, яка під унікальним кутом розповідає про будні мафіозних сімей та кримінального світу загалом.
При досить довгому сюжеті, але коротких місія гра, проходить Мафія за 15-20 годин.
Брат Джоела виявився куди витривалішим за рядових супротивників і витримав навіть постріли з арбалета і підпалювання вогнеметом.