1985 was the beginning of a ground breaking period for the company. After buying three Boeing 757 aircraft, the airline started to plan flights to Europe for the first time. That period culminated with the opening in 1990 with their first route to the old continent, when they started services to Frankfurt, Germany. In between, the company also opened flights to Taipei in 1986, and Dubai in 1988, all using the newest jet on their fleet.
By then, the airline's rapid expansion made it a necessity to sell the 737s and buy Boeing 767 aircraft. The first delivery of this type of aircraft for Royal Brunei broke a world record when it flew 17 hours and 55 minutes non stop from the Boeing company in Seattle to Jomo Kenyatta International Airport in Nairobi, Kenya., on its way to Brunei.
Seven more 767s were delivered, taking the fleet to eight 767s and two Boeing 757's. 1991 also saw the opening of a route to Jeddah.
In 1993, Abu Dhabi, Cairo, Zürich, Beijing and Bahrain were added to the ruote system. In 1994, it was Brisbane, Miri, Labuan, Osaka and Balikpapan's turn to join. 1995 saw the airline arriving at Calcutta and in 1996, Royal Bruniei's jets began making their way to Bintulu and Yangon.
Several of these routes would later have to be cut off because of government or economic restrictions, among them, Cairo and Osaka.