This early ICAO document covering the introduction of GNSS (GPS) should cover the whole topic quite well. I would skip to section 3 (page 75) Information on Fiji’s Early Application of GPS Technology. But the highlights are effectively:
Fiji consists of 300 islands (mostly volcanic) scattered over 200 000
square miles of ocean. Of these, only 100 are inhabited. There are
nineteen airfields, plus seven that are privately owned, but only five
of the nineteen have NDBs and one has VOR-DME. This means that 80 per
cent of the area is without any form of navigation aid. There are also
helicopter and seaplane operations. Navigation has been accomplished
primarily through visual flight rules or dead reckoning.
...
Fiji became involved in FANS and GPS in 1990/91 through briefings given by CAA Australia, and became
convinced of the safety and cost benefits to be gained. Ad hoc trials, including long distance oceanic flights with a
hand-held GPS receiver convinced Fiji of the potential of the GPS.
...
Under a Memorandum of Co-operation (MOC) the United States FAA provided equipment and operational and
technical support to carry out trials and demonstrations. GPS receivers were provided for installation in all domestic
IFR aircraft. These early receivers were not certified, and special procedures were developed to ensure that all the
information provided by the GPS was confirmed by other navigation sources.
...
Some of the main features are listed here.
• GPS routes had been designed to all nineteen aerodromes. The GPS route charts show GPS airways and GPS
way-points at the intersections.
• GPS checkpoints were established and surveyed on all the aerodromes, initially using a GPS receiver but
now these have been resurveyed by an outside contractor to WGS-84.
• Outside areas of VOR/DME coverage, the pilot DR is now replaced by GPS procedures.
• Cloud break procedures were also designed to enable pilots to descend below cloud and make visual contact
with the island, so that in most cases they leave a pilot at 1 000 ft above obstructions, five miles out, on the
extended centre line. This information together with way-points were entered into the GPS receivers via data
cards, by the CAA Fiji.
• Pilots and controllers were trained and examined on the rules and procedures. Pilots also had to undergo a
practical test before being approved and pilots may not use the GPS unless they are approved.
• Based on this initial experience, the charts have been further simplified so that pilots can now select, on the
GPS receiver, straight-in approach or cloud break, when this was needed.
This early 90's advertisement for Trimble GPS units also makes claims to being the ones that were used on these first approaches.
According to the document Fiji basically moved everything over to GPS; en-route navigation, approaches, the whole shebang. This helped them fly safer in IFR and have way more coverage than their limited ground based beacons gave them. The US helped not only create procedures, plates and information but also equipped all Fiji based operators and airfields.