In Regatul Nou, cea de-a XVII-a Dinastia a decid sa ii respinga pe hicsosi. Au folosit medjay ca infanterie si cercetasi. Probabil ca recompensa pentru slujirea in razboi, multi medjay s-au stabilit pe pamanturile egiptene. Serviciul militar in timpul dinastiiilor XVII si XVIII le-a castigat o binemeritata reputatie.

Dupa serviciul miltar, au evoluat intr-o forta de mentinere a pacii. In curand, ei au ajuns foarte bine organizati si instruiti, in forte politienesti.

Egiptenii se laudau cu faptele lor din viata in morminte. In Regatul Nou intalnim titluri precum “seful Medjay” chiar in necropola din THeba. Deci titlul ajunsese de admirat. Ei continua si in timpul domniei lui Akhenaten, ca servitori civili. Un alt oficial din dinastia XVIII, Amenemone, a detinut titlul de “sef al Medjay”, pe langa cel de “Comandant al Armatei”, “Mesager Regal in Toate Tarile Straine” si “Administrator al Lucrarilor din Ramesseum”.

Invatatii moderni de azi reconsidera viziunea despre Medjay ca politisti. Ei au gasit in mormintele si atelierele de la Deir el-Medina, ca medjay arestau hotii de morminte, livrau mesaje, pazeau satele, colectau taxele si protejau mormintele si localnicii. Erau implicati si in grevele muncitorilor si erau trimisi in zonele mai putin populate.

Politia s-a transformat incet in forta militara. Medjay au luptat cu invadatorii libieni Meshwesh in nordul Deltei in timpul domniei lui Ramesses al IX-lea. Mai tarziu, in Regatul Nou, termenul “medjay” a disparut. Oare au fost ei asimilati populatiei egiptene? A incetat sa existe aceasta profesie militara? Nimeni nu stie. Insa un grup relativ apropiat de Medjay, numit Mededs, a luptat impotriva kushitilor in secolul al V-lea i. Hr.

In secolul al III-lea d. Hr, un grup de razboinici neinfricati, numiti Blemmyes au iesit din Nubia opunandu-se romanilor. Pliniu cel Tanar, povesteste in Istoria Naturala, ca multe popoare africane sunt deabia umane, iar Blemmyes nu sunt deloc diferiti. El pretinde ca acestia nu au capete, gurile si ochii le sunt asezate pe piept.

Ii descrie ca nomazi, putin numerosi si deloc razboinici. Au fost numiti asa pentru ca erau hoti si atacau persoanele fara aparare. Ca si Medjay, acesti Blemmyes, sau Beja, isi serveau ocupantii – in acest caz, romanii. Insa erau separati de un mileniu de sange si traditie. Nu vom sti niciodata sigur daca acesti erau Medjay sau nu.