Graham was elected to replace his retiring father in a by-election in 1998. Following the New Brunsiwck general election of 1999, Graham's Liberal Party was reduced to 10 seats from 44. This gave the young politican the chance to quickly raise to prominence.
He was named the caucus chair of the party and became one of the most vocal and popular critics of the government of Bernard Lord.
Liberal leader Camille Theriault resigned in March of 2001 and a leadership convention was set from May of 2002. Few candidates emerged for this campaign and it appeared that former cabinet minister Paul Duffie would win virtually unopposed. Graham was urged to run and eventually entered the race with the support of Greg Byrne, a previous leadership contender and many of the supporters of Bernard Richard, also a former leadership contender and the interim leader following the resignation of Theriault.
Surprising many pundits, Graham was successful in taking a solid lead during delegate selection meetings in February and March of 2002 and, as a result, Duffie dropped out of the race. This left only fringe candidate Jack MacDougall in the race who Graham defeated by a 3 to 1 margin at the May convention.
Graham was considered a lightweight by pundits and by the governing Progressive Conservative Party and few gave him a chance in the coming election. Though Graham's Liberal Party of New Brunswick and the PCs were near each other in the polls, Graham was a relative unknown and trailed Premier Bernard Lord by signifigant margins.
Graham surprised pundits again during the New Brunswick general election of 2003, running an energetic campaign and winning 26 of 55 seats.