On returning to this country, he received a letter of service for raising a regiment in his native country, of which he was appointed Lieutenant-Colonel Commandant on the 10th February, 1794, and which having been since retained on the establishment of the army, is now the Ninetieth Light Infantry, or Perthshire Volunteers. This regiment formed part of the army under the command of Lord Moira (afterwards Marquis of Hastings). It passed the summer of 1795 at Isle Dieu, whence it proceeded to Gibraltar. On the 22nd of July, 1795, the rank of Colonel in the Army was conferred on Lieutenant-Colonel Graham. He continued for some months with his regiment at Gibraltar, when he obtained permission to join the Austrian Army. His connexion with that service continued during the summer of 1796, taking the opportunities which his position presented him of sending to the British Government intelligence of the military operations and diplomatic measures adopted by the commanders and sovereigns of the Continent: his despatches at this period evinced, in a remarkable degree, the great talents and characteristic energy of the writer. During the investment of the city of Mantua by the French, he was shut up there for some time with General Wurmser, but, impatient of remaining inactive, he succeeded in making his escape, under cover of night, encountering great difficulty and imminent hazard. Early in the year 1797, he returned to England, but in the following autumn rejoined his regiment at Gibraltar, whence he proceeded to the attack of Minorca with Sir Charles Stuart, who bestowed the warmest eulogiums on the skill and valour displayed by Colonel Graham. The part which he took in the reduction of Minorca is thus described in a work, published some years ago, detailing those transactions:-- "After the debarkation of the troops innumerable difficulties opposed themselves to their operations. There is not in any part of Europe to be found a greater variety of natural obstacles to an invading army than in this island. Reports from deserters and others, contradictory in their purport, rendered General Stuart for a short time irresolute what course to pursue. He, however, resolved to proceed by a forced march to Mercadel, and by possessing that essential post, to separate the enemy's force. To effect this object, Colonel Graham was sent with 600 men, and by dint of the utmost effort arrived at Mercadel, a very few hours after the main body of the enemy had marched towards Candarello. Here he made a considerable number of prisoners, seized several depôts of ammunition, &c., and established his corps in front of the village. The reduction of Minorca being completed, Colonel Graham repaired to Sicily, where he employed himself in the service and for the assistance of its legitimate monarch; and such were his exertions, that he received repeated acknowledgments and tributes of gratitude and esteem from the King and Queen of Naples."