Graham's 1993 victory was a key test for his Progressive Conservative Party of New Brunswick. His party had been defeated provincially in 1987 going from having led the government for 17 years to being shut out of the legislature. Though the party regained 3 seats in the 58 seat legislature in 1991, the upstart Confederation of Regions Party of New Brunswick (CoR) had won 8 seats and claimed official opposition. Graham's victory was seen as a sign that CoR would not necessarily displace the Progressive Conservatives as the voice of conservatism in Anglophone New Brunswick.
In 1999, Graham's party was returned to government. Graham, who co-chaired the election campaign, was named deputy premier and Minister of Supply and Services. On July 21, 2005, Graham added the responsibilities of Minister of Environment & Local Government on an acting basis when his cabinet colleague Brenda Fowlie was forced to resign from the cabinet. He retained the portfolio until November 21, 2005.
His party failed to win a plurality of seats in the 2006 election so Graham left cabinet and returned to opposition. He was re-elected in 2010 and his party returned to government, and he became dean of the legislature; he was excluded from cabinet but was elected to serve as speaker of the legislature. He did not seek re-election in 2014.