Working together: over cigars, California Governor Arnold Schwarzenegger and Speaker Fabian Nunez build an unlikely bond.

In late 2003, Republican Governor Arnold Schwarzenegger rode into office promising to "blow up" state bureaucracy and go over the heads of California's liberal Legislature. A few months later, Fabian Nunez, an outspoken critic of the new governor, took over as speaker of the Democratic-run state Assembly. "I have declared political war on Schwarzenegger," Nunez said at the time.

Now, Governor Schwarzenegger calls Nunez his "great friend." The 59-year-old governor and the 40-year-old speaker often talk over cigars in the smoking tent the governor has set up in a courtyard of the Sacramento Capitol building. Politically, the two have come together to forge deals on raising the state's minimum wage, rebuilding infrastructure and passing a landmark anti-global-warming bill. Amid continuing criticism from their own parties, they're tackling thorny areas including health-care reform.

After a failed effort to ram a conservative agenda through the Legislature early in his tenure, Governor Schwarzenegger shifted sharply to the center last year. Since this conversion to what he calls "post-partisanship," the governor has been basking in the glow of mounting popularity. But arguably, much credit for California's new era of bipartisanship, one of the most productive periods in the state legislature's recent history, belongs with Nunez.

"I am a results-oriented person," the governor said in an interview. "So is the speaker."

Their journey toward rapprochement--one part political calculation, another part personal ties forged over cigars in the governor's backyard helps--explain why California is beginning to solve problems that have vexed the Golden State for years.

The state is becoming something of a national model for how the two parties can work together even after years of acrimony, and Nunez and Schwarzenegger have attracted the attention of the 2008 presidential campaigns. Two Republican contenders, Arizona Senator John McCain and former New York Mayor Rudolph Giuliani, have visited Governor Schwarzenegger to seek his advice on bridging partisan differences, aides for the campaigns say. In April, New York Senator Hillary Clinton named Nunez one of 10 national co-chairs of her presidential campaign, a job that calls for national campaigning and fund raising.

"He was able to demonstrate leadership and get the Republicans in California to go along with him," said Mo Elleithee, a spokesman for Senator Clinton. "That is lacking in Washington."

Nunez and Schwarzenegger share an outsider's perspective: The governor came to the United States as a struggling bodybuilder from Austria. Nunez was born in the United States, one of 12 children of Mexican-immigrant parents. But in many ways, they are opposites. While Governor Schwarzenegger rode to power with a celebrity's name recognition and a conservative mandate on many issues, Nunez worked his way out of a San Diego barrio.

In 1973, Nunez's parents moved the family from Tijuana, Mexico, to San Diego's Logan Heights neighborhood to give their children a better education. His father, Pablo, worked as a gardener; his mother, Soledad, as a maid. Nunez was born in San Diego, making him eligible for U.S. citizenship.

Nunez walked to school from the family's two-bedroom apartment, negotiating junkyards and transients. "The odds were totally against him," says Rachael Ortiz, executive director of Barrio Station, a youth center where Nunez went after school to practice for Golden Gloves boxing competitions. Nunez says many of his friends ended up in prison. "Somehow I slipped through the cracks," he says.

BRAWL WITH GUARDS

After attending the University of California at San Diego on an academic scholarship, and going on to graduate from Pitzer College in Claremont, Calif., he went to work helping Latino immigrants assimilate in the United States, in part by teaching them English. Later, in Los Angeles, he organized for a local gas-workers union and the AFL-CIO, once getting into a brawl with four guards during a labor dispute. Antonio Villaraigosa--a former California state Assembly speaker and now mayor of Los Angeles--helped groom Nunez to run for his old Assembly seat in a low-income district that includes East Los Angeles.

Nunez was elected to the Assembly, the lower house of California's Legislature, in 2002. His charm and negotiating skills impressed people on both sides of the aisle. "On day one, people kept talking about this young kid from L.A.," says Jim Brulte, then the Republican minority leader of the state Senate.

In an October 2003 special election, Governor Schwarzenegger unseated Democratic incumbent Gray Davis, who was recalled by voters over his inability to deal with a huge state budget gap, among other problems. Two months later, Nunez was nominated speaker of the state's lower house. He took office in early 2004.

The two locked horns immediately. The former actor used his action-hero persona to take on the state's financial problems, telling voters to "terminate" legislators at the polls if they didn't go along with his budget. Nunez and others in the Democrat-led Legislature fought his attempts to reduce funding for education and social services. Nunez was quoted by a Mexico City newspaper as saying he had declared war on the governor on immigration issues, vowing to fight Governor Schwarzenegger's attempts to keep undocumented immigrants from applying for driver's licenses. (Nunez says he was misquoted by the newspaper, La Cronica; the paper did not respond to written requests for comment.)

In 2004, Governor Schwarzenegger derided the Democratic legislators for refusing to sign off on his budget. He called them "girlie men." Nunez shot back in a Sacramento Bee article that quoted him as saying: "I don't know that he wears lifts--I know that's the rumor. I don't even know that he wears makeup--I know that's the rumor."

But behind the scenes, the two men had already begun to forge more cordial ties. In December 2003, Governor Schwarzenegger hosted a dinner at his mansion in the Brentwood section of Los Angeles in Nunez's honor. One of the governor's actor friends, Danny DeVito, was there. At one point, the speaker recalls, Governor Schwarzenegger suggested that Nunez join him in his backyard to smoke cigars. "I remember walking out there and thinking, 'This is a pretty big backyard,'" Nunez says. "Then DeVito looks over and says, 'Do you mind if I join you?' I said, 'Of course--you're Danny DeVito.'"

Governor Schwarzenegger also popped into the speaker's office when Nunez's parents were in town, and paid a visit to Nunez's new home in a suburban tract in Sacramento. "I knew right away when the torch was passed to him that he is the person I need to deal with," the governor said.

GOVERNOR'S END-RUN

In public, the clashes continued. The governor in 2005 attempted to do an end-run around the Democrats by taking his conservative drive directly to voters through a series of ballot initiatives. The measures would have curbed the power of Democratic-leaning unions to make political contributions, for example, and would have made it easier to fire teachers.

"This is a governor who wants the power to be king," Nunez said that summer on PBS's "News Hour with Jim Lehrer." He called the initiatives an attack on working people. "I came at him very hard," says Nunez. "I took him on on everything."

In July 2005, Governor Schwarzenegger invited Nunez to his Brentwood home in a bid to head off a showdown over the measures. The pair retired to patio chairs beside Governor Schwarzenegger's backyard pool to smoke cigars--the governor wearing shorts, sandals and a polo shirt, the speaker in khakis. At one point, Nunez recalls, the governor turned to him and began talking about their common backgrounds. "He said, 'You and I are both immigrants,'" says Nunez. "He let his guard down a lot with me, and his attitude was really about, 'How do we make this work?'"

The two failed to work out a political compromise that day.

By August, Governor Schwarzenegger's popularity had dropped to 36 percent, compared with over 60 percent after he was elected. In November 2005, California voters roundly defeated the ballot measures. With gubernatorial elections only a year away, many believed Governor Schwarzenegger had no chance of re-election. Nunez, having helped trounce the governor, saw his political capital soar.

Fellow Democrats urged the speaker to press for advantage. Major contributors including the California Teachers Association, the California Correctional Peace Officers Association and the state's trial-lawyers association--advised him to keep attacking ahead of the 2006 polls. (A spokeswoman for the lawyers' group, the Consumer Attorneys of California, said she was not aware of such lobbying from her association and said it isn't the group's practice to tell politicians what to do.) "The easiest thing for me to have done, politically, would have been to jump on the anti-Arnold bandwagon and take it all the way to the governor's election," Nunez says.

The speaker knew that while the governor's approval ratings were low, the state Legislature's numbers were lower still: The same survey that showed Governor Schwarzenegger's popularity had plummeted, a Field Poll of registered voters, showed that only 27 percent of respondents thought the state Legislature was doing a good job. Democratic lawmakers could have faced a backlash from voters if they had blocked progress in Sacramento, Nunez says: "I would have wasted a whole year."

Soon after the initiative debacle, Nunez says the governor confided to him that he would chart a more conciliatory course with the Democrat-dominated Legislature. In a meeting in the governor's first-floor office a few days after the election, Governor Schwarzenegger brought together Nunez, State Senate President pro tempore Don Perata and the two Republican legislative leaders. "He told us, 'That's over with. Let's get to work,'" says Kevin McCarthy, then leader of the Republican minority in the Assembly. Soon after, the governor announced he was replacing his Republican chief of staff with a Democrat. "Political courage is not political suicide," Governor Schwarzenegger says of the turnabout.

By this time, Nunez had become a regular visitor to the governor's cigar-smoking tent. In one such visit shortly after the November elections, the speaker suggested a bill he had recently agreed to sponsor that would cap greenhouse gas emissions in the state. "I told the governor, 'Here's what I want to do,'" Nunez recalls. According to the speaker, the governor's eyes lit up. 'He said, 'I'm a Republican, but I'm a Hollywood Republican.'"

Governor Schwarzenegger had already taken stands to protect forests and water quality. On the global-warming bill, he faced opposition from his own party in California because many Republicans said businesses would have to spend more to comply with its measures. The governor agreed to sign the bill only if the state would consider letting businesses use market-based approaches to capping emissions, such as trading pollution credits. The governor signed the bill in 2006, turning him into a world-wide environmental hero and gaining him recognition as the "Green Governor."

Governor Schwarzenegger's alliance with Nunez has made both men targets of criticism within their own parties. Last year the governor drew opposition from one of his biggest supporters, the California Chamber of Commerce, when he threw his support behind a Democratic bill that would raise the state minimum wage from $6.75 an hour to $8, the highest in the country, by 2008. Business leaders complained the increase would hurt state businesses. Governor Schwarzenegger addressed some of their concerns when he rejected a Democratic provision that would have tied future increases to inflation.

PRO-LABOR FEATHER

When the minimum-wage bill was signed into law on Sept. 12, 2006, Nunez appeared at the governor's side and thanked him for his leadership. Governor Schwarzenegger referred to Nunez as "my great friend."

The law stung some Democrats: Coming just a few weeks before the state's November gubernatorial election, the wage increase was seen as adding a pro-labor feather to Governor Schwarzenegger's cap at the expense of the Democrats' own candidate, then-state Treasurer Phil Angelides. Nunez was co-chair of Angelides's Democratic campaign.

"The effect of Fabian working with the governor undermined the ability of the Democratic candidate," says Donna Berger, director of government relations for the California Nurses Association, a 75,000-member union, which was instrumental in helping defeat the governor's reform initiatives in 2005.

Nunez says he campaigned hard on Angelides's behalf. He also acquiesced to requests from many in the party, terminating his appearances with Governor Schwarzenegger in the final weeks before the election, which the governor won by a landslide. But Nunez said that deals such as raising minimum wage shouldn't wait for politics. "I said, 'Look, this will help poor people,'" Nunez says.

Jim Carlton is a writer for The Wall Street Journal. This article, which ran in the Wall Street Journal May 31, 2007, was reprinted with permission.