Began in 1672, as a Lieutenant in Sir William Lockhart's Scots Regiment. This regiment was under the command of the Duke of Monmouth in the service of the French King Louis XIV. By 1674, Graham was a Cornet in William of Orange's guards. He was present at the Battle of Seneffe and rescued the young Prince when his horse fell in marshy ground. As a reward for his actions Dundee received a Captain’s commission. Two years later Graham resigned his commission and returned to Scotland. William wrote a letter to James, Duke of York (later James VII), who was both his uncle and father-in-law, recommending James Graham as a soldier.
Graham was appointed captain by Charles II in 1678 with orders to suppress conventicles (Lowland Presbyterian meetings) that the king deemed seditious. His reputation for relentless repression of the Covenanters, as they are known today, in Dumfries and Galloway earned the nickname of “Bluidy Clavers”. The difficulties of his task, the hostility of the populace, and the nature and extent of the country he was required to watch were too great for the leader of a small body of cavalry, and in spite of his vigorous and energetic action, Graham accomplished little. He conducted his occupation with zest, however, and interpreted consistently the orders he received, acting as both judge and executioner. In 1685 he summarily executed John Brown for his refusal to acknowledge the supremacy of the King.
On 1 June 1679 the Covenanters routed him and his army at the Battle of Drumclog, whereupon he fled to Glasgow, successfully defending it until his party left on 3 June, heading towards Stirling. Later joined by the Duke of Monmouth, the whole of the militia, and two regiments of dragoons, both sides met again at the Battle of Bothwell Brig, on 22 June, and the Covenanters were convincingly routed. In 1680 he was despatched to London to influence the king against the indulgent method adopted by the Duke of Monmouth with the extreme Covenanting party. The king seems to have been fascinated by his loyal supporter, and from that moment Graham was destined to rise in rank and honors. Early in 1680 he obtained a royal grant of the barony of the outlawed Macdougal of Freuch, and the grant was after some delay confirmed by subsequent orders upon the exchequer in Scotland.
In January 1681 he was appointed to the sheriffships of Wigtown, Dumfries, Kirkcudbright and Annandale. In December 1682 Graham was appointed colonel of a new regiment raised in Scotland. He had still greater honors in view. In January 1683 the case of the earl of Lauderdale was debated in the House of Lords. Lauderdale was proprietor of the lands and lordship of Dundee and Dudhope, and the decree of the Lords against him was in March 1683 issued for the sum of 72,000 pounds. Graham succeeded in having part of the property of the defaulter transferred to him by royal grant, and in May he was nominated to the privy council of Scotland.
Surprisingly, he married Lady Jean Cochrane, a daughter of a fiercely Covenanting family in 1674. Shortly after the death of Charles II in 1685, Graham incurred a temporary disgrace by his deposition from the office of privy councillor; but in May he was reinstated, although his commission of justiciary, which had expired, was not renewed. In 1686 he was promoted to the rank of major-general, and had added to his position of constable the dignity of provost of Dundee. In 1688 he was second in command to General Douglas in the army which had been ordered to England to aid the falling dynasty of the Stuarts. In 1688, however, he was created Viscount Dundee by James II while with the Scots army in England.