1882 nahm er am Anglo-Ägyptischen Krieg unter General Wolseley zur Niederschlagung der Urabi-Bewegung teil. Am 28. August wurde seine 2.000 Mann starke Brigade beim Marsch nach Kassassin von der Armee Urabi Paschas bei Mahsama angegriffen. Obwohl diese zahlenmäßig fünffach überlegen war, konnte Graham standhalten. In Anerkennung seiner Leistungen wurde er am 18. November 1882 als Knight Commander des Order of the Bath (KCB) geadelt und führte fortan das Prädikat „Sir“.[1]
In Sudan war 1881 der Mahdi-Aufstand ausgebrochen und der Mahdi-General Osman Digna hatte das Heer von Baker Pascha am 4. Februar 1884 bei El-Teb geschlagen und die Forts von Tokar und Sinkat eingeschlossen. Graham landete deshalb im Februar 1884 mit 5.000 Mann bei Suakin, um die wichtige Küste des Roten Meeres zu sichern. Die Soldaten gehörten größtenteils zur British Indian Army, hatten an der Besetzung Ägyptens teilgenommen und waren nun auf dem Rückweg nach Indien. Graham konnte Osman Digna in der Schlacht von Teb am 29. Februar schlagen und erreichte am 3. März Tokar. Am 13. März war Graham in der blutigen Schlacht von Tamanieh erneut siegreich. Als sich General Grahams Truppen später im Jahr aus dem Sudan zurückzogen, gewann Osman Digna seinen alten Einfluss aber zurück. Am 21. Mai 1884 wurde Graham für diesen Einsatz zum Lieutenant-General befördert.
Nach dem Fehlschlagen der Gordon Relief Expedition von Garnet Joseph Wolseley, wurden die britischen Truppen aus Sudan abgezogen, nur Graham wurde 1885 erneut nach Suakin beordert. Er hatte den Auftrag, mit 13.000 Mann wiederum gegen Osman Digna vorzugehen. Außerdem hatte er die Aufgabe, von Suakin über Berber an den oberen Nil vorzudringen und den Bau einer Eisenbahnstrecke zur Verbindung dieser beiden Orte zu ermöglichen. Am 20. März 1885 besiegte Graham Osman Digna bei Tamai und Hashin. Von der geplanten Eisenbahnlinie waren 1886 19 englische Meilen ausgebaut, als die Kriegsaussichten mit Russland die britische Regierung veranlassten, das Unternehmen aufzugeben. Im Mai verließ Graham Suakin und kehrte nach England zurück. Großbritannien versuchte erst rund zehn Jahre später durch den Feldzug Horatio Herbert Kitcheners, Sudan erneut zurückzuerobern und die Mahdisten zu schlagen. Am 25. August 1885 wurde er als Knight Grand Cross des Order of St. Michael and St. George (GCMG) ausgezeichnet und schließlich am 20. Mai 1896 auch zum Knight Grand Cross des Order of the Bath (GCB) erhoben.[1]
Graham starb am 17. Dezember 1899 in Bideford, Devon, drei Wochen nachdem die Mahdisten bei Umm Diwaykarat endgültig vernichtet wurden. Sein Victoria-Kreuz liegt im Royal Engineers Museum in Gillingham, Kent.
