During 1998 and 1999, "Labuan" made four deployments to Bougainville Island as part of Operation Bel Isi: March to April and August to October in 1998, and January to March and July to August in 1999. In between these deployments, the ship continued on a program of training exercises and logistical support for other defence units. "Labuan" sailed to Dili, East Timor on 18 September 1999 as part of INTERFET. The ship provided logistic support, beach landing capability, and rest facilities for INTERFET forces. She remained in the area until 14 October, and was redeployed in support of INTERFET during November–December 1999, February–April 2000, June–July 2000, August–September 2000 and November–December 2000. These deployments were later recognised with the battle honour "East Timor 1999–2000". On returning to Cairns at the end of 2000, the ship was prepared for a Life of Type Extension refit; the refit itself lasted from late February 2001 to early September 2001. On 15 October, "Labuan" sailed on another deployment to Bougainville, under Operation Bel Isi II.