Even though he objected many of the practices and missions they executed, President Obama has shown confidence in many of the Bush-era military and intelligence leaders, and looked for ways to keep them in his administration.
The latest is FBI Director Robert Mueller, who the president would like to stay on another two years. Thursday Obama announced he was seeking Congressional approval to keep Mueller, who has led the FBI since just before 9/11, in place.
"In his ten years at the FBI, Bob Mueller has set the gold standard for leading the Bureau. Given the ongoing threats facing the United States, as well as the leadership transitions at other agencies like the Defense Department and Central Intelligence Agency, I believe continuity and stability at the FBI is critical at this time," Obama said in a statement.
The president also asked for Defense Secretary Robert Gates to stay at the Pentagon when Obama first came into office. Gates was one of two Republicans in the president's cabinet. The secretary was former President George W. Bush's pick to lead the military after Donald Rumsfeld left at the peak of chaos in Iraq.
Another military chief who Obama has leaned on is General David Petraeus. Petraeus led the Iraq troop surge and was credited with helping turn the war around for the Bush administration. Obama was against this strategy at first, but has since acknowledge its success. Petraeus was appointed by Obama to serve in several capacities including taking over as the top commander in Afghanistan after General Stanley McChrystal resigned amid a damaging interview.
Obama has now nominated Petraeus to lead the CIA.
Many of the missions these men oversaw - enhanced interrogations, Guantanamo Bay, the Iraq War and surge, the mission in Afghanistan -- Obama was critical of on the campaign trail and even while president.
It's not uncommon in times of war for presidents to look for stability and avoid making sweeping changes, but it's ironic he's been so vocal about many of the policies these leaders took part in.
"Remember we have a change at CIA, we have a change at the Defense department, this willingness of director Mueller to continue to serve for 2 more years help provide continuity which is important," White House Press Secretary Jay Carney also noted Thursday.
Some Republicans have argued that the killing of Usama bin Laden was able to happen under Obama's watch because of Bush-era policies.
Obama has argued that in the past resources were diverted with missions like the war in Iraq from focusing and being able to capture bin Laden.
Sen. John McCain, R-Ariz on Tuesday said that he didn't think enhanced interrogations like water boarding led to getting bin Laden. McCain, who was also a prisoner of war in North Vietnam for several years, was responding to assertions made by former Attorney General Michael Mukasey.
When asked last week if the White House could say with certainty that bin Laden's hideout wouldn't have been found without enhanced interrogation, Carney said that there wasn't one item or technique that tipped them off and multiple avenues were used.
"I can say with certainty that no single piece of information, with the exception of the address of the compound, was vital to this -- was singularly vital to this -- because we're talking about tiny bits of information that were compiled by unbelievably competent professionals over nine and a half years," Carney said.
House Judiciary Committee Chairman Lamar Smith, R-Texas, says that Mueller was very deep into the intelligence about bin Laden and other potential terror threats. He says that the killing of bin Laden and subsequent intelligence dump was one of the reasons why the administration kept Mueller on board.
Congress will have to write legislation for Mueller to stay on longer than the appointed ten-year tem. They'll have write that legislation soon and pass it in late May or early June.
Fox News' Anne McGinn and Chad Pergram contributed to this report.