The South Arabian Army (SAA) were the heirs to a proud tradition of locally raised forces in the Protectorates. During the First World War, hundreds of local Arabs were recruited to oppose the encroaching Turkish forces and in 1926, when the Royal Air Force took over the responsibility for controlling this hinterland, a force of levies was raised to guard the RAF installations. This force, called The Aden Protectorate Levies (APL), was commanded by British officers, save that the subalterns and NCOs were largely recruited from up-country Arab tribes. This bias meant that there was little chance of merging the levies with other local militias around the town of Aden. Consequently, the APL conducted few operations within the urban environment of Aden. During the Second World War and into the 1950s the Levies expanded and were increasingly important in patrolling, piquetting heights and guarding convoys crossing rebellious tribal areas in the Western Aden Protectorate.

It was often the attraction of regular employment in a poverty-stricken land that drew many soldiers into the Arab army. Yet, the soldiers of the APL, or The Gaysh as it was known, were highly rated by their British commanders. According to Brigadier Charles Dunbar, Brigadier General Staff, this army was relatively independent compared to the armed forces of most Arab countries. But the tribal pull was strong and remained so during the time of British control. Lieutenant-Colonel Sandy Thomas, who commanded a battalion of the APL, recalled that his local men were ‘smart, keen, willing and cheerful and expert in their own art of soldiering in this forbidding country’. However, they were often subject to malign influences during their one month's leave. ‘They often have to walk ten days or more to reach their tribal area’, Thomas observed, ‘as there are no roads or vehicles. Then, when they arrive they find themselves embroiled in tribal affairs, usually concerning some blood feud’.

In 1959 the Federation of South Arabia was created, and it was decided that the APL should be closely tied to it. In line with this, two years later the APL was renamed the Federal Regular Army (FRA) and attempts were made to convert it to an all-Arab force. At formation, the only remaining British officers were the overall commander, Brigadier James Lunt together with his four battalion commanders. By 1964 all battalion commanders were Arab, though British NCOs were retained to help train new recruits, and in that year, a fifth battalion was added to the force, with Brigadier Gordon Viner taking over as overall commander.