The naval component of the F-FDTL was established in December 2001 when Portugal transferred two small Albatroz-class patrol boats from the Portuguese Navy. Its establishment was not supported by the King's College study team, the UN, or East Timor's other donor countries on the grounds that East Timor could not afford to operate a naval force. The role of the naval component is to conduct fishery and border protection patrols and ensure that the maritime line of communication to the Oecussi enclave remains open. All of the force's warships are based at Hera Harbour, which is located a few kilometres east of Dili. Under the Force 2020 plan the naval component may eventually be expanded to a light patrol force equipped with corvette-sized ships and landing craft.
On 12 April 2008 East Timor signed a contract for two new Chinese-built 43-metre Type-62 class patrol boats. These ships were to replace the Albatroz-class vessels and to be used to protect East Timor's fisheries. The contract for the ships also involved 30 to 40 East Timorese personnel being trained in China. The two new patrol boats arrived from China in June 2010, and were commissioned as the Jaco-class on the eleventh of the month. In November 2010 it was reported that East Timor would order a further two patrol boats from South Korea. In the event, three ex-Republic of Korea Navy Chamsuri class patrol boats were donated, and these entered service with the naval component on 26 September 2011. The East Timorese government also ordered two fast patrol boats from the Indonesian company PT Pal in March 2011 for the price of $US40 million.
In 2017 Timor-Leste accepted an offer of two new Guardian class patrol vessels and associated training and logistics assistance from the Australian Government. The vessels are scheduled to be delivered in 2023.