Игра получила преимущественно положительные отзывы критиков. Оценка PC-версии на агрегаторе оценок Metacritic составила 77 из 100. GameRankings на основании 31 рецензии поставил игре оценку 77,19 %.
Mafia II на протяжении двух недель была самой продаваемой в Великобритании.
В некоторых обзорах было высказано недоумение отсутствием ожидаемых возможностей, которые не дошли до окончательного варианта. Так, в статье Eurogamer отмечается, что открытый мир игры не является «в достаточной степени открытым», так как у героя нет второстепенных заданий; автор также плохо отозвался о боевой системе. По словам автора этого ресурса, «Mafia II уничтожает миф о том, что мафия вообще интересна. Игра утверждает, что мир населён глупыми роботами, которые каждое утро просыпаются, делают повторяющиеся действия и идут домой».
Журнал PC Gamer UK поставил игре оценку 78 %, но отметил, что «За 10 часов преступлений 2K Czech показали идеальную элегию по фильму о мафии. Однако нужно было сделать больше самой игры».
Рецензент сайта GameSpot, Кевин ВанОрд (англ. Kevin VanOrd), в своей рецензии также отмечает «недостаточно открытый мир, слишком большое количество рутинных миссий».
Авторы «Игромании» в рецензии, опубликованной на сайте, отрицательно отозвались об игровом процессе, описав его как «перегоны из точки А в точку Б», в то же самое время отметив «поражающую» детализацию мира: «каждая подворотня, каждый фасад в Эмпайр-Бэй вылеплены вручную (…) то и дело оглядываешься по сторонам, поражаясь детализации интерьеров, а спускаясь по лестнице, можно встретить подслушивающую под дверью уборщицу, которая тут же смущается от нашего появления (…) дотошности 2K Czech не перестаёшь удивляться даже во второй и третий раз»; в обзоре на сайте игра была оценена в 7,5 из 10, в то же время в «альтернативном мнении» она получила 9,5 из 10, а обзор был подытожен словами: «в мире этой игры хочется жить, причём слово „жить“ здесь следует понимать не в том смысле, который обычно вкладывают в него игры типа Gotһіс или Oblivion. Здесь не задержишься надолго, зато те несколько дней, которые мы проводим вместе с Вито и Джо, стоят многих месяцев блужданий по фэнтезийным лесам».
Крайне негативно отозвался об игре рецензент сайта Absolute Games Владимир Горячев, также известный как Nomad. Поставив игре 54 из 100 %, автор описал игру как «трещащую по швам», с «неинтересным миром», «убогим финалом», а главных героев Nomad назвал «овощем» и «слизняком». Также автору было сложно проходить игру, так как была отмечена «частая гибель от шальных выстрелов».
Прямо противоположное мнение было высказано в статье известного сайта 3DNews. Журналистка издания очень положительно отзывается о различных аспектах игры, в том числе сюжете, графике, игровом процессе, называя Mafia II «предложением, от которого невозможно отказаться». Автор подводит итог сравнениям с серией GTA такими словами:
«Mafia II никак не вписывается в прокрустово ложе подражательства и вторичности, куда вталкивают её критики — дескать, Grand Theft Auto в антураже сороковых, да и только. Несмотря на схожую игровую механику, это — два абсолютно разных проекта. Творение 2K Czech напоминает классические голливудские гангстерские ленты. Свет, лениво струящийся сквозь жалюзи. Клубы табачного дыма в холодных отблесках вывесок. Изрядно початая бутылка виски на столике возле дивана. Серьёзные мужчины в шляпах и с револьверами за пазухой, роковые женщины… Меланхоличный закадровый голос, отпускающий комментарии с изрядной долей чёрного юмора. Далёкий вой полицейской сирены, и чей-то труп, истекающий кровью… Каждая сцена в игре наполнена смыслом, идеально поставлена и отснята. Здесь нет безликих и неинтересных персонажей. Каждый герой представляет собой сложную многогранную личность. Причём это в равной степени относится как к главным действующим лицам, так и к второстепенным. Обратите внимание на старушку-мать, которая молится перед скудным обедом, беспокоится за судьбу своего сына Вито и по утрам обзванивает его закадычных друзей, чтобы узнать, где он ночевал и устроился ли на честную работу». «Общее впечатление» — «блестящее произведение!»
Летом 2018 года, благодаря уязвимости в защите Steam Web API, стало известно, что точное количество пользователей сервиса Steam, которые играли в Mafia II хотя бы один раз, составляет 2 312 872 человека.
В феврале 2020 года бывший член семьи Коломбо Майкл Франчезе, который отсидел в тюрьме 10 лет за рэкет и отмывание денег, по предложению издания BuzzFeed провёл обзор геймплея игры и поставил ей оценку 4,5 по 10-балльной шкале, отметив ряд нестыковок и ляпов со стороны разработчиков в плане описания возможных действий главного героя, начиная от драк и заканчивая взломом сейфов.
Вышедшее в 2020 году Definitive Edition было неоднозначно встречено игроками и игровыми изданиями. На Metacritic ПК-версия была оценена несколько ниже, чем оригинальная версия для той же платформы — 74 балла из 100 возможных, в то время, как версии для PlayStation 4 и Xbox One получили смешанные отзывы от прессы — версии переиздания для данных платформ получили 57 и 63 балла соответственно. Первые игроки негативно восприняли переиздание, в основном, из-за «сырой» сборки — многие игроки отмечали баги игры и проблемы с графикой даже на консолях с максимальной комплектацией.