Wyraz policja jest zapożyczeniem z łac. politia, a to z grec. politeía ‘obywatelstwo, państwo, rząd’, od grec. polités ‘obywatel’. W polszczyźnie poświadczony jest od XVI w. w formie policya (wymawiany [po-li-cy-ja]). Początkowo oznaczał sztukę rządzenia państwem lub miastem, o czym świadczą m.in. cytaty ze „Słownika języka polskiego” S. B. Lindego, np. „Policya z grec. znaczy rządzenie miastem, państwem” (S. Petrycy, Ekonomia), „Policya, rząd wolny Rzeczypospolitej” (A. Frycz Modrzewski) oraz „Policya, rozrządzenie wewnętrzne bezpieczeństwa, spokojności, wygody miast i krajów” (S. B. Linde). Funkcjonował też jako synonim wyrazów polityka, np. „Pewniejsza, dokładniejsza i narodowi pożyteczniejsza nie może być jakakolwiek policja handlu (to jest polityka handlowa) jak ubezpieczona i żadnemi granicami nie określona wolność handlu” (K. Stronczyński, Słownik warszawski), oraz porządek publiczny, por. np. „Miasta policji niechaj strzegą” (S. Staszic, Słownik języka polskiego pod red. W. Doroszewskiego).
Jak podaje A. Bańkowski w Słowniku etymologicznym języka polskiego, nowe znaczenie wyrazu policja ‘straż pilnująca porządku publicznego’ zaczęło się rozwijać we Francji, odkąd (w XVII w.) franc. police stało się nazwą osobnego urzędu królewskiego.
W Polsce dopiero sejm w Grodnie w 1793 r. ustanowił osobną komisję policji, por. „Komisya policyi ustanowiona do utrzymywania powszechnego w kraju porządku, tak co do bezpieczeństwa i spokojności, jako i co do wygody publicznej”. W zależności od tego, czym dokładniej zajmowała się dana komisja (urząd), wydzielano m.in. policję miejską, wiejską, państwową (czyli żandarmerię), wodną, rzeczną, wykonawczą, śledczą, poprawczą.
Wyraz policja rozszerzał swój zakres znaczeniowy i oprócz znaczenia ‘urząd policyjny’ określał również ‘osoby tam panujące; policjanci’, a także ‘budynek, w którym ten urząd się mieścił’.
Policja jest wyrazem o charakterze internacjonalnym, por. np. ros. polícyja, niem. Polizei, hol. politie, franc. police, ang. police, włos. polizia, hiszp. policía.
W bliskim związku z policją pozostaje milicja, także XVI-wieczne zapożyczenie, z łac. militia, od mīles ‘żołnierz’; hist. ‘wojsko o charakterze korporacyjnym, np. miejskie, duchowne’, także ‘straż przyboczna królów i możnowładców’; ‘straż ochotnicza’, i znacznie nowsze: ‘w Polsce komunistycznej organizacja podobna do policji, odpowiedzialna za ochronę porządku i bezpieczeństwo ludzi’.