New Attorney General Michael Mukasey is aggressively trying to mend fences on Capitol Hill following a bruising confirmation battle and the savaging of the Justice Department’s senior command during Democrats’ first year in the majority.

Attacked for refusing to define waterboarding as torture during his confirmation hearings, Mukasey has shelved any animosity he might feel toward Democrats for nearly sinking his Senate confirmation and is trying to make the best of his year in office.

“We’re cautiously optimistic that we’ll be able to work well with Congress going forward,” said Peter Carr, the department’s new principal deputy director of public affairs and the former chief spokesman for Sen. Orrin Hatch (R-Utah).

Mukasey is “reaching out to Members of Congress and building relationships with them — Republicans and Democrats,” Carr added. “Our direction from him is to work things out, whenever possible.”

After a surprisingly heated nomination fight that focused on the meaning of torture, Mukasey was confirmed, 53-40, on Nov. 8, with a half-dozen Democrats supporting him in what was the narrowest confirmation for an attorney general since 1952.

Now, Mukasey is reaching out to friend and foe alike — calling lawmakers to inform them of nominees to fill department vacancies and U.S. attorney slots. Since being confirmed, Mukasey has met with the chairman and ranking members of the Senate and House Judiciary committees, as well as key members of those panels. He thanked Democrats who broke ranks to support him on the Senate floor, but he is also forging ties to those who opposed him.

Before being confirmed, Mukasey paid a courtesy call to House Judiciary Chairman John Conyers (D-Mich.). Though they got along personally, Justice Department aides said, the House is particularly partisan and Conyers already has criticized the department for failing to provide a witness for a hearing on the rape of a contract worker in Iraq, and for not appointing a special counsel in the CIA tapes case.

On the Senate side, Mukasey will make his debut before the Judiciary Committee — including Chairman Patrick Leahy (D-Vt.), who opposed his nomination over the torture issue — when it holds its first oversight hearing toward the end of January.

“The relationship between the attorney general and the Judiciary Committee is still developing, and there are outstanding requests from the chairman and others for information and cooperation,” Senate Judiciary spokeswoman Erica Chabot said.

Sen. Sheldon Whitehouse (D-R.I.), an influential Judiciary Committee member who also opposed Mukasey, said the new attorney general had impressed so far.

“From my perspective, the preliminary signals are good ones, although given the depth of the rot at the Department of Justice, it’s going to take a good deal more until I’m assured that the Department of Justice is back on the straight and narrow,” Whitehouse told Roll Call.

Whitehouse said the ultimate test for Mukasey would be how he resolved the torture question, although lawmakers would also be interested in the reports issued by Justice’s inspector general on various internal matters stemming from the U.S. attorneys probe.

Whitehouse said he penned a letter to Mukasey wishing him well after his confirmation. Just before the holidays, he got a call from Mukasey advising him that he would be releasing new regulations limiting the number of contacts between Justice and the White House, which Whitehouse had expressed concern about.

“That was very nice. That was a personal touch,” Whitehouse commented.

Mukasey’s overtures are being buttressed by former Hill aides who joined Justice over the summer: Brian Benczkowski, a former senior counsel to then-House Judiciary Chairman Jim Sensenbrenner (R-Wis.) and ex-aide to Sen. Pete Domenici (R-N.M.), came on board in July as the deputy assistant attorney general at the Office of Legislative Affairs. Carr, the former chief spokesman for Hatch, is the new No. 2 in the Justice press shop.

Mukasey also has taken several steps welcomed by former critics to rebuild the reputation of a department battered by a year of scandal following the sloppy firings of nine U.S. attorneys in 2006. Sensational hearings and public pressure resulted in the resignation of top Justice aides, including Attorney General and Bush confidant Alberto Gonzales.

Five days after assuming office, Mukasey reopened an investigation into the Bush administration’s warrantless wiretapping program. Most recently, he launched a criminal probe into the CIA’s destruction of tapes depicting the interrogation of high-profile terrorist detainees, earning kudos from Democrats and the press.

Although he initially praised him, Leahy ultimately opposed Mukasey because the nominee refused to classify waterboarding as torture.

Nonetheless, Leahy and Mukasey have talked several times since his confirmation and the attorney general reached out to invite Leahy and his chief counsel, Bruce Cohen, to the lighting of the National Menorah during the holidays, which Mukasey presided over.

“The new attorney general’s view is whether we’re going to agree or disagree on the merits, I want to have a good personal relationship with Pat Leahy,” one Justice Department aide said.

Mukasey also reached out to another potentially powerful enemy: Senate Majority Whip Dick Durbin (D-Ill.), calling Durbin to inform him that Mark Filip, a district judge from Chicago, would be the administration’s pick as the new deputy attorney general.

Despite initial praise, Filip ran into the same problem as Mukasey — he refused to declare waterboarding illegal during his confirmation hearings — drawing the ire of Democrats, including Durbin.

Mukasey and Justice officials also consulted with Minnesota Sens. Norm Coleman (R) and Amy Klobuchar (D) before the White House nominated career prosecutor Frank Magill to take over for Rachel Paulose, the controversial former head of the Minnesota U.S. attorney’s office.

But Justice officials are not naive about the challenges they face with only a year left in the Bush presidency and a Democratic majority unafraid to wield its oversight power, especially during a presidential election year.

Several legislative battles are brewing, not the least of which are possible Senate and House floor fights over contempt citations in the U.S. attorney matter against ex-Bush political guru Karl Rove, White House Chief of Staff Joshua Bolten and former White House counsel Harriet Miers.

Congress is set to take up amending the Foreign Intelligence Surveillance Act, which regulates wiretapping, one of Mukasey’s top priorities, aides said. In December, Mukasey came to the Hill to deliver a classified briefing to any lawmaker who wished to participate in conjunction with the Office of Director of National Intelligence.

Mukasey also must deal with a raft of vacancies requiring Senate confirmation, including the controversial nomination of Steven Bradbury as head of the Office of Legal Counsel. Democratic lawmakers are still fiercely opposed to Bradbury’s ascension.