В конце Max Payne, Макса арестовывают. Однако Альфред Уоден исполняет обещание, которое дал Максу очень давно. Являясь сенатором, он освобождает Макса.

Несмотря на свободу, Макс не может найти мир: его сны и мысли продолжают прокручивать воспоминания о смерти семьи. Он не совсем психически и эмоционально здоров. В дополнении, Макс внутри разочарован, что избежал правосудия.

Два года спустя, он возвращается в полицию Нью-Йорка, как детектив по расследованию убийств. Очередное расследование сталкивает его с Моной Сакс, женщиной, которую он считал погибшей и которую втайне любил.

Мона подозреваемая в деле по убийству Себастьяна Гейта, расследуемого детективом Валери Винтерсон, новым напарником Макса. После того как Макс встречается с Моной, чтобы получить информацию относительно связи его расследования и дела Винтерсон, лейтенант Джим Бравура, шеф Макса, с огнестрельными ранениями попадает в больницу. Это задерживает расследование Макса. Когда Мона сбегает из тюрьмы во время нападения бандитов, Макс объединяется с ней (и снова попадает в розыск). Вместе, они понимают, что развернувшаяся война банд в Нью Орке вероятно спровоцирована Винни Гоньитти, который пытается захватить чёрный рынок по продаже оружия. Одной из главных группировок, участвующих в войне являются Уборщики, маскирующиеся наемники. Эта организация носит такое название, потому-что чистит все признаки своей деятельности: гильзы, обоймы, трупы, кровь.

Пробравшись в грузовик Уборщиков, Макс проникает в их штаб-квартиру: огромную строительную зону. Он общается с Моной через радио-наушник. Она тоже проникает на стройку и они вместе с боем пробираются через недостроенные здания. На стройку приезжает детектив Винтерсон и ловит Мону. Мона клянется Максу, что Винтерсон приехала, чтобы убить её. Макс встает перед выбором. Наконец, он стреляет в Винтерсон и позволяет Моне убежать. Перед смертью Винтерсон успевает несколько раз выстрелить Максу в спину. Их обоих доставляют в больницу. Винтерсон умирает, но Макс остаётся в живых. Для того, чтобы убить его в больницу приезжают Уборщики.

Вскоре Макс и Мона понимают, что за действиями Уборщиков стоит Владимир Лем. Хотя, Лем клялся, что он завязал с преступностью и занялся ресторанным бизнесом, он тайно управлял русской мафией в Нью-Йорке. Он нанял Уборщиков, чтобы устранить своих конкурентов, включая Винни Гоньитти. Когда Уборщики терпят неудачу в убийстве Гоньитти, Лем решает сделать все сам и использует хитрый план. Он закладывает взрывчатку в голову костюма Капитана Бейбольной Биты, любимого героя Винни. Винни одевает костюм и понимает, что если он снимет голову куклы, то она взорвется. Хотя Макс защитил Винни от убийц, ворвавшихся в его дом, они оба попадают в плен к Лему.

Лем насмехается над Максом, раскрывая невероятную тайну. Николь Хорн и Лем были членами Внутреннего Круга, которым Лем хотел завладеть после смерти Уодена. Он также говорит, что Мона киллер, нанятый Уоденом, чтобы убить Макса и Лема. Лем также говорит, что именно Уоден послал секретные планы проекта Вальгалла жене Макса, и следовательно. виновен в её гибели. Макс не может в это поверить. Влад стреляет Максу в голову, и затем нажимает кнопку на детонаторе, взрывая голову Гоньитти. Здание охватывает пожар.

Лем отставляет Макса умирать в огне, но Мона спасает Пэйна. Понимая, что Лем направиться к Уодену, чтобы убить его, Пэйн и Мона пробираются в особняк Уодена и с боем пробиваются через орды Уборщиков, чтобы защитить старого Сенатора. Добравшись до нужного места, Мона вдруг сообщает Максу, что она была нанята Уоденом, чтобы убрать беспорядок — включая Макса. Она наводит пистолет на Пэйна, но не может нажать на курок, только бьет Макса рукояткой по голове. Неожиданно появляется Лем и стреляет в Мону; Уоден выбирается из своего тайника, извиняясь перед Максом, он нападет на Влада и тот стреляет в него. Лем взрывает бомбы, установленные по всему особняку. Макс преследует Влада по горящему и рушащемуся дому. Лем забирается на платформу обозрения в огромном зале и пытается поджечь Макса, кидая в него коктейли Молотова. Но Макс обрушивает на платформу тяжёлый шпиль, висевший под потолком. Платформа обрушивается на пол, тело окутывает огонь.

Когда пребывает полиция, Макс возвращается к Моне. Мона умирает (в наиболее сложном уровне концовка другая, более оптимистичная), но мучения Макса успокаиваются.

«Это только начало Боли... Путешествие Макса сквозь ночь продолжится…»