Помимо системы навигации, обновлённый радар изменил систему уровней розыска полицией. Теперь полицейские не прибывают в место нахождения протагониста игры. В GTA IV при увеличении уровня розыска на радаре появляется круг, очерчивающий некоторую территорию относительно места совершения преступления или места, в котором игрок был последний раз замечен полицией. Чем выше уровень розыска, тем больше радиус круга. Полицейские автомобили и вертолёты также фиксируются радаром. Чтобы уйти от погони, необходимо выйти за рамки круга и продержаться там некоторое время. Если игроку удаётся покинуть зону розыска, то «звёзды розыска» начнут мигать и если игрока не заметят другие полицейские — то пропадут. Если же игрока заметят, то центр области розыска автоматически смещается на место, где находится протагонист игры. Также в отличие от предыдущих частей игры даже на первом уровне розыска число полицейских не ограничено одним, и все работники охраны правопорядка, заметившие главного героя, будут пытаться его арестовать. Полицейские больше не бьют протагониста дубинкой или кулаками, а просто его арестуют. Даже если Нико Беллика начнут арестовывать, существует выбор: подчиняться и дать себя арестовать или вырваться, повысив тем самым свой уровень розыска на одну «звезду». Начиная с третьего уровня розыска к погоне за игроком подключается вертолёт и полицейские внедорожники «Patriot», полицейские сооружают баррикады из своих машин на дорогах. На четвертом уровне розыска к попыткам остановить игрока присоединяется специальное подразделение NOOSE (англ. National Office Of Security Enforcement, аналог SWAT). Начиная с пятого уровня розыска к погоне присоединяются агенты FIB (аналог ФБР) и второй полицейский вертолет. На последнем шестом уровне розыска, в отличии от предыдущих частей игры, отсутствуют военные силы и танки, а преследованием игрока занимают очень многочисленные сотрудники полиции.

В связи с возможностью войти в состояние алкогольного опьянения, и интересен тот факт, что полиция начинает преследование, если видит нетрезвого персонажа за рулём. При этом, если автомобиль не движется, то блюстители правопорядка не проявляют интереса.