In late 1795 the regiment went to Gibraltar on garrison duty, a role Graham soon tired of. He obtained permission to join the Austrian army on the Rhine as British Commissioner. In this capacity he shared in the disastrous campaign of 1796, and afterward assisted Wurmser in the defence of Mantua, when it was besieged by the French under Napoleon. The garrison was reduced to the greatest extremities from want of provisions, and Graham undertook the perilous duty of conveying intelligence to the Imperial General Alvinzi, at Bassano, distant, of their desperate situation.