The vote came after two key Democrats accepted his assurance to enforce any law Congress might enact against the tactic of waterboarding.
The former federal judge, nominated in September by President Bush to replace Alberto Gonzales, had been under intense questioning by committee members over prisoner interrogation tactics and the constitutionality of torture, specifically waterboarding or simulated drowning.
Mukasey's assurances on torture won the support of judiciary panel members Sens. Dianne Feinstein, D-Calif., and Charles Schumer, D-N.Y. The full Senate vote is likely to take place before Thanksgiving and could come as early as this week.
Feinstein said her vote came down in part to practicality. If Mukasey's nomination were killed, she said, Bush would install an acting attorney general not subject to confirmation and make recess appointments to fill other empty jobs at the Department of Justice.
"I don't believe a leaderless department is in the best interests of the American people or of the department itself," Feinstein said.
Committee Chairman Patrick Leahy, D-Vt., however, was not persuaded by Mukasey's testimony. "Unsaid, of course, is the fact that any such prohibition [of waterboarding] would have to be enacted over the veto of this president," Leahy said.
Some Republicans, as well, appeared uneasy with some of Mukasey's answers on torture. During confirmation hearings, Mukasey said he was not familiar with the waterboarding technique and could not say whether it was torture.
Sen. Arlen Specter, R-Pa., called Mukasey's explanation "a flimsy excuse" and suggested that Mukasey declined to call waterboarding torture because he wanted to avoid putting U.S. officials at legal risk. Specter voted in favor of Mukasey.
In an interview last week with the NewsHour, Sen. Lindsey Graham, R-S.C., said, "You've got a suspicious Congress, I guess... .When [Mukasey] said the technique was repugnant to him personally, it made me feel better. ...So, yes, I'm very inclined to support him, but I understand the suspicion."
Senate Republicans and the White House press secretary called for a swift confirmation vote.
"We appreciate the vote of senators on the Judiciary Committee to forward the nomination of Judge Michael Mukasey to the full Senate," White House press secretary Dana Perino told reporters. "Judge Mukasey has clearly demonstrated that he will be an exceptional attorney general at this critical time."