O'Malley says Democrats can win an argument for a more progressive vision than they've pushed in the past. That's what he's done in Maryland, where he walloped challenger Bob Ehrlich by 14 points in 2010, despite raising a host of taxes in his first term, and not just on the wealthy.
O'Malley has raised income taxes, sales taxes, alcohol taxes, car fees, even the sewer "flush" fee, while pushing for casinos across the state and a gas tax increase to boot.
That record has made him a juicy target for conservatives and for some of his in-state Democratic rivals as well who believe he's gone too far. But it's made him a hero to many on the left.
O'Malley knows tax increases are not the typical path to political success, and not what any consultant would advise someone with aspirations for higher office to push.
Indeed, one adviser told O'Malley when he was considering whether to propose a gas tax increase before this year's legislative session that it would be a "double kill shot to your head," one Maryland source said, and O'Malley pushed ahead anyway.
He acknowledges that people generally oppose taxes in polls unless the tax won't affect them.
"Of course," he said. "That's always true. That's human nature. That's where leadership comes in. Or instead, we could elect leaders that tell us we can eat cake and lose weight, that everything's a free lunch."
O'Malley said the country has been dramatically undercapitalized as a result.
"We have to as a people make investments in a shared future that we can only make together," he said.
O'Malley is quick, however, to leaven the tax hike narrative by arguing that he's cut waste and spending as well to balance the books during tough economic times.
"We have applied a balanced approach," he said. And he points to what those tax increases have helped accomplish - among them, well-funded, top-ranked schools and state college tuition that hasn't budged in four years, as well as programs expanding health care coverage and cleaning up the Chesapeake Bay. He says that Maryland's state and local tax burden as a percentage of income is the third-lowest in the nation.
Nationally, O'Malley speaks out against the Bush tax cuts for the wealthy but tends to indict them in general.
And he makes a Kennedy-esque appeal to pitching in to the country.
"The more we give, the more effort we put into making our nation strong, the more she gives back to us, the more she gives back to our children, the more she gives back to our grandchildren," he said. "That's what it means to be an American. ... You want to live in the greatest country in the world, or do you want to pass out the JV jerseys? I want to live in the greatest country in the world."
O'Malley's harder-line approach does have its admirers.
Sen. Tom Harkin (D-Iowa) is a fan, inviting O'Malley to headline his steak fry this year.
Rep. Elijah Cummings, D-Md., right, hugs Harold Schaitberger, General President of the International Association of Fire Fighters, after the Congressman spoke at the IAFF's Legislative Conference General Session at the Hyatt Regency on Capitol Hill, March 9, 2015. The day featured addresses by members of Congress and Vice President Joe Biden.