Progressive Conservatives merged with the Canadian Alliance as the Conservative Party of Canada in early 2004, and Nicholson joined the new party. He was narrowly returned to parliament in the 2004 election, defeating Liberal Victor Pietrangelo by more than 1,000 votes. Nicholson served as Shadow Transportation Critic from July 2004 to January 2005. He was appointed Chief Opposition Whip on January 28, 2005. During the 38th Canadian Parliament, he was one of only two members of the 99-member Conservative caucus in the Commons who had previously served in the federal cabinet. Harper government (2005-2015) Nicholson was re-elected in the 2006 election and appointed to the Harper cabinet as Government House Leader. Minister of Justice (2007-2013) Nicholson was appointed as Minister of Justice and Attorney General of Canada in early 2007. He replaced Vic Toews as Justice Minister during a Cabinet shuffle on January 4, 2007. Peter Van Loan replaced Nicholson as Government House Leader. On March 13, 2010, Nicholson released the terms of reference for the appointment of Frank Iacobucci as an Independent Adviser. Iacobucci will conduct an independent review of documents related to the transfer of detainees by the Canadian Forces in Afghanistan. This statement comes after Richard Colvin spoke before a parliamentary committee stating that he warned for a full year that detainees Canadian troops handed over to Afghan forces faced torture before the government began to monitor them. “London, The Hague and Canberra [Australia] are deeply concerned about the absence of solid legal protections for detainees, which – in the age of Gitmo and Abu Ghraib – imperils domestic support for the Afghanistan mission,” said the memo of December 4, 2006, written by diplomat Richard Colvin. Amir Attaran also brought forward testimony in stark contrast to then Canadian Ambassador to Afghanistan David Sproule's. Afgan prisoners testified that after capture by Canadians, they were subsequently handed to the custody of the Afghan National Army (ANA), claiming they were later been abused by the ANA. Minister of Defence (2013-2015) In the July 15, 2013 cabinet shuffle, Nicholson switched portfolios with Peter Mackay and became the Minister of Defence. Minister of Foreign Affairs (2015) Because of John Baird's resignation, Harper was forced to reshuffle his Ministry on 9 February 2015. An unexpected beneficiary of the Baird defalcation was Nicholson, who was promoted to Minister of Foreign Affairs (Canada). Nicholson's time as head of the Canadian Foreign Service was cut short