W GTA: GBA tak jak w poprzednich częściach z serii będziemy mieli problemy z policją. Służby porządkowe w miarę zwiększania się poziomu poszukiwań, będą coraz bardziej liczne, coraz bardziej pomysłowe, jak również coraz lepiej uzbrojone. W GTA GBA wyróżniamy cztery poziomy poszukiwań przez policje. W górnym rogu ekranu będą pojawiać się takie oto twarze funkcjonariuszy - Tyle ile będzie twarzy, tak jest twój obecny stopień poszukiwań przez policję.


Pierwszy stopień poszukiwań otrzymać można w bardzo prosty sposób. Jeżeli uderzy się w policyjny radiowóz, zabije policjanta, jak również za zabicie innego człowieka w obecności funkcjonariusza policji. Pozbyć się pierwszego stopnia poszukiwań jest jeszcze łatwiej niż go "zdobyć". Wystarczy schować się między budynkami, czy pokręcić się trochę po mieście skręcając w różne zakręty etc.

Drugi stopień poszukiwań otrzymać można za zabicie kilku policjantów lub grupki ludzi na oczach funkcjonariusza. Jednak technika "w chowanego" nie ma w tym wypadku zastosowania. Drugiego stopnia poszukiwań można się pozbyć tylko odwiedzając lakiernika.

Jeżeli policja nie będzie mogła cię złapać, a ty w dalszym ciągu będziesz terroryzować miasto i likwidować kolejnych obywateli, wtedy otrzymasz trzeci poziom poszukiwań. Na drogach pojawią się blokady, co utrudni ci ucieczkę. Jeżeli chcesz się pozbyć "ogona" to tak jak w wypadku stopnia drugiego, przemaluj brykę.

Czwarty poziom poszukiwań jest najwyższy w całym GTA : GBA. Jeżeli będziesz naprawdę sprytnym przestępcą i policja nie będzie mogła cię uchwycić, to "w nagrodę" otrzymasz czwarty stopień poszukiwań przez policję. Funkcjonariusze uzbroją się w karabiny maszynowe oraz będą niszczyć twoje wozy, zwiększy się ich liczebność i w pewnym stopniu inteligencja. Uważaj na siebie i gnaj do lakiernika, chyba że chcesz się trochę pobawić.