В октябре 1996 года имя Николсона вновь угодило в скандальную хронику. Согласно газетным сообщениям, произошло следующее. Актер вернулся к себе домой из Нью-Йорка, где состоялась премьера его фильма "Старые друзья". Поскучав в одиночестве полдня, он позвонил старому другу, вернее, подруге девочке по вызову Кэтрин Шихан. Последняя дала себе зарок никогда больше не появляться в доме актера, после того как однажды тот отдубасил ее на пьяную голову. Но Николсон всегда славился умением убалтывать кого угодно. Вот и в этом случае ему понадобилось всего лишь несколько минут, чтобы умаслить девушку и заставить ее забыть старые обиды. Однако для подстраховки та все же приехала не одна, а прихватила с собой одну из напарниц.

Когда девушки приехали к Николсону, тот пообещал заплатить им за ночь любви по тысяче долларов каждой. Но обманул. Когда все было закончено и актер удовлетворенно лежал на постели, Кэтрин напомнила ему про деньги. И тут же пожалела об этом. Не успела фраза о деньгах слететь с ее губ, как хозяин дома вскочил и набросился на девицу. Что было дальше, Кэтрин всю жизнь будет вспоминать с ужасом. По ее словам, Николсон сначала бил ее головой об пол, а когда она попыталась добраться до телефона, чтобы вызвать полицию, исцарапал ей силиконовую грудь, а потом вышвырнул из дома. Добравшись до своего автомобиля, путана все-таки вызвала к месту происшествия копов, но те не нашли в случившемся ничего предосудительного и укатили восвояси. И все же Кэтрин отомстила Николсону за свой позор, поведав эту историю журналистам.

Летом 1998 года Николсон завел себе очередную любовницу - 28-летнюю актрису Лару Флинн Бойл (известна по телесериалу "Твин Пикс"), которая до этого крутила романы с Кайлом Маклахленом, Ричардом Дином Андерсом и Дэвидом Спэйдом. Девушка настолько запала в душу актеру, что он стал осыпать ее дорогими подарками, возил на Лазурный берег. Год спустя они даже торжественно отметили годовщину своего знакомства. А потом пара внезапно распалась, причем по вине Лары, которая внезапно увлеклась Брюсом Уиллисом (тот как раз ушел от своей жены Деми Мур). Но этот роман оказался скоротечным, и Лара вскоре опять запросилась к Николсону. Как ни странно, тот ее принял. Более того, когда газеты засекли Лару в компании другого голливудского сердцееда - Харрисона Форда, - Николсон и тогда не стал раздувать из мухи слона и ни словом не упрекнул свою возлюбленную.

В новогоднюю ночь 1999 года Николсон и Лара были приглашены в Белый дом на вечеринку. По словам очевидцев, Николсон был в тот вечер в ударе и флиртовал со всеми мало-мальски симпатичными женщинами. Лара стоически держалась, понимая, что устраивать скандал в таком месте неприлично. Но когда они вернулись в отель, она дала волю своим эмоциям. Говорят, шум от скандала стоял такой, что на него сбежалась охрана. Когда секьюрити ворвались в номер, полагая, что там происходит смертоубийство, они застали нелицеприятную картину: Лара металась по номеру как пантера, а на полу лежал сломанный стол и осколки вдребезги разбитой пепельницы. Разъяренную женщину едва удалось успокоить. В дальнейшем таких конфликтов будет еще несколько, однако на взаимоотношениях возлюбленных это никак не отразится они будут продолжать жить вместе.

В июле 2001 года Николсон был приглашен в качестве почетного гостя на Московский кинофестиваль. Приехал он сюда не один, а вместе с Ларой. Говорят, у нее так и не сложились отношения со старшей дочерью Николсона 36-летней Дженнифер (та считает, что Лара позарилась исключительно на деньги отца), зато она ладит с детьми актера от Ребекки Бруссар.