RMAF Labuan started with the deployment of one detachment of the Royal Air Force, under the command of Group Captain S.J.

After the formation of Malaysia on 16 September 1963, some personnel were deployed to this airbase under the Air Force Borneo.

At that early time, RMAF Labuan owned some Twin Pioneer aircraft for logistic and patrol role.

In 1966, RMAF Labuan received its first batch of DHC-4 Caribou to strengthen the No 8 Squadron that already operated Twin Pioneer transport aircraft.

The No 5 Squadron that formed in Kuala Lumpur also moved to the RMAF Labuan with their Aérospatiale Alouette III helicopters to provide a rotorcraft element.