The word "starboard" actually precedes "right" and "left" in English usage, while "port" is newer. The first entry the OED has for "starboard" is this:

eOE Acct. Voy. Ohthere & Wulfstan in tr. Orosius Hist. (BL Add.) (1980) i. i. 14:

He..let him ealne weg þæt weste land on ðæt steorbord & þa widsæ on ðæt bæcbord þrie dagas.

whereas "right" and "left" both seem to appear about 1200-1225:

c1225 (?c1200) Sawles Warde (Bodl. 34) (1938) 22

Þe middel sti bituhhe riht & luft.

(If you're confused about that, sound it out -- "the middle is between right and left")

a1225 (?OE) MS Lamb. in R. Morris Old Eng. Homilies (1868) 1st Ser. 141

Þer stod a richt halue and a luft alse an castel wal.

It's generally thought that "starboard" is a word formed from some version of "steering-board," that is, the place where one would steer a ship; we think that steering oars on e.g. Norse and northern European ships were on the right (starboard) side of the boat.

What's interesting about that top entry is that you can see that the starboard ("steorbord") is opposed here to "bæcbord," or back-board; by the time we get to Middle English, "laddeborde" has supplanted "bæcbord" and will slowly drift into "larboard":

c1400 (▸?c1380) Patience l. 106 Þay layden in on laddeborde & þe lofe wynnes.

1495 in M. Oppenheim Naval Accts. & Inventories Henry VII (1896) 203

Devettes..j a sterbord an other a latebord.

15.. Sir A. Barton in Surtees Misc. (1888) 69

A larborde wher Sir Andrewe lay.

1582 R. Stanyhurst tr. Virgil First Foure Bookes Æneis i. 4

Theire ships too larboord doo nod.

1591 W. Raleigh Rep. Fight Iles of Açores sig. B2,

Two on her larboord, and two on her starboord.

1598 in R. Hakluyt Princ. Navigations (new ed.) I. 4

Vpon his steereboord alwayes the desert land, and vpon the leereboord the maine Ocean.

a1600 Sir A. Barton in Surtees Misc. (1888) 68

Ethere bye lerbord or by lowe That Scootte would overcome yowe.

1667 Milton Paradise Lost ii. 1019

When Ulysses on the Larbord shunnd Charybdis.

The issue with "starboard" and "larboard" is that if you're trying to quickly distinguish between them, especially with giving orders in say a storm or other place where you can't hear or be heard well, they can sound a great deal like one another. The word "port" starts being used in opposition to "starboard" around the Tudor era. Again from the OED:

1543–4 High Court of Admiralty Exam. 11 Jan. (Rypper's Depos.) 92

The sayd [ship] mighte have layed his helme a porte.

1633 T. Stafford Pacata Hibernia iii. viii. 312

With two takles hee might steere the Hoy either to Starboard, or to Port.

1644 H. Mainwaring Sea-mans Dictionary

To Port. Is a word used in Conding the Ship,..they will use the word steddy a-Port, or Steddy a Star-boord, the Ship heeles to Port: bring things neere to port, or the like.

The substitution of "port" for "larboard" is made official in 1844:

1844 Admiralty Order 22 Nov.

The word ‘Port’ is frequently..substituted..for the word ‘Larboard’, and as..the distinction between ‘Starboard’ and ‘Port’ is so much more marked than that between ‘Starboard’ and ‘Larboard’, it is their Lordships direction that the word ‘Larboard’ shall no longer be used.