Medjay
The Medjay were mercenaries of Ancient Egypt. Pastorialists from Medja (a part of Nubia) came to Egypt for employment, including as mercenaries, as far back as the Old Kingdom (c. 2686 BC - c. 2181 BC), although their prominence as established mercenary units probably began during the Second Intermediary Period (c. 1650 BC - c. 1550 BC), where their fighting prowess gained recognition and they were an important contributor to Egypt's military power.
By the 18th Dynasty (1549/1550 BC - 1292 BC) they were well established as an elite paramilitary police force, with tasks ranging from desert scouting to pharaonic guards. Gradually the term "Medjay" shifted from being an ethnic one to an occupational one, as anyone who fulfilled the requirements could become a Medjay - this is evidenced by the increasing incidence of Egyptian names in their roster.
More sources:
Habiru
The Habiru were described in various ancient Near East sources as nomads with various occupations, including mercenaries, but also things such as rebels, raiders, outlaws, and migrant laborers. They may have been related to early Hebrews (the same, or the Habiru includes Hebrews, or they just happen to have similar names).
The earliest mention dates to around 1850 BC, describing them as small bands of soldiers, apparently mercenaries serving local city-states. Another mention is on the Tikunani Prism, describing events around 1550 BC, and lists the names of 438 Habiru soldiers serving a local King.