The Medjay are mentioned in the Egyptian records as early as the Old Kingdom, when the term is used to denote a group of desert tribesmen in *Nubia who became scouts and light-armed auxiliaries in the Egyptian army. By the First Intermediate Period it is evident that they are still in the military service, since an inscription at the Hatnub quarry mentions them among the followers of the prince of the Hermopolitan nome.
By the Eighteenth Dynasty, this term simply comes to mean a 'policeman'. The Medjay were men who patrolled and guarded the desert frontiers, protected the cemeteries and undertook general duties to maintain order throughout Egypt. They even acted as law enforcement officers and protected the royal necropolis workers' village at Deir el Medina. The senior police officer in charge of the force was called 'Chief of the Medjay', and in each large town there was a police force under the control of a 'Captain of the Medjay.' By the New Kingdom, the term 'Medjay' no longer implied a person of *Nubian origin and many of them were now undoubtedly of native Egyptian stock.
BIBL. Davies, N. de G. The Tombs of Two Officials ofTuthmosis the Fourth. EES. London: 1923.
Biographical Dictionary of Ancient Egypt by Rosalie and Antony E. David
Ancient Egypt. A Reference Guide. EdwART. 2011.