The PNTL was established in May 2002 by the United Nations, before sovereignty was passed to the new state, with a mandate to provide security and maintain law and order throughout the country, and to enable the rapid development of a credible, professional and impartial police service.

Recruitment drives were conducted in early 2000, and basic training commenced on 27 March 2000, under the auspices of the United Nations Transitional Administration in East Timor (UNTAET).

It was not until independence, on 20 May 2002, that an agreement was signed outlining the terms and timetable for handing over of full policing duties from CivPol to the PNTL.

[3] In August 2017, the PNTL is criticized by Fundasaun Mahein for allowing its officers to be visible with heavy weapons since it undermines the force's community policing strategy.

[4] On 18 November 2018, PNTL officer José Mina, shot dead three young men during a party in the neighborhood of Kulu Hun in Dili.