Texas Rep. Sam Johnson and Arizona Sen. John McCain have had a complicated relationship in Congress, despite the fact the Republicans were once cellmates in the infamous Hanoi Hilton during the Vietnam war.

Johnson endorsed George W. Bush for president in 2000, calling his fellow war hero “too liberal.” He also worked tirelessly to defeat McCain’s “blanket amnesty” immigration bill in 2007, telling the San Antonio Express News, “hopefully this bill will never see the light of day again” when it fell in the Senate.

In the Gingrich years, he helped lead a group of right-wing rebels, founding the Conservative Action Team, an antecedent to the Republican Study Committee. And to this day, an “immigration” page on Johnson’s website begins with his longtime adage, “If you break the law, you should be deported.”

So it has baffled even the staunch conservative’s close allies that he is participating in bipartisan negotiations on an immigration fix with liberal Democratic Reps. Xavier Becerra of California and Luis V. Gutierrez of Illinois.

To wit, Johnson was the secretive group’s founding Republican member.

In March 2009, Becerra approached Johnson, asking if he wanted to discuss the issue broadly. The two had become friends while serving on the Smithsonian Institution’s Board of Regents, as well as on the Ways and Means Committee.

With the initial talks going well, the two discussed bringing in other members. But first, Johnson got the prodding of a rather influential Republican: then-Minority Leader John A. Boehner of Ohio.

“Boehner and I talked and he asked me to do it, and I said I would,” Johnson said when asked to explain his initial involvement.

That admission illustrates how the man who is now speaker had a significantly more important role in helping create the working group than has previously been disclosed.

Senate Jokes Break the Ice

With encouragement from leadership, Johnson began recruiting Republicans on the House floor, starting with a fellow conservative Texan, Rep. John Carter, who colleagues refer to as “Judge Carter” thanks to his years in the 1980s as a district court judge in Williamson County, Texas.

Carter is as conservative as Johnson and the two are quite close; they attend a Christian retreat together once a year.

Former Reps. Lincoln Diaz-Balart and Adam H. Putnam were also brought into the circle, and the Republicans met among themselves to discuss their negotiating strategy.

When the original Republicans and Democrats finally came face to face, “like any of these kind of meetings, the first few minutes are like a couple of dogs circling each other,” recalled Putnam, who is now serving as Florida’s agriculture commissioner and is a potential future gubernatorial candidate.

The improbable collection of liberals and conservatives broke the ice with jokes about how lame the Senate is, an ever-popular topic among members of the House.

For almost four years after that, the group would meet in secret, its ranks swelling to as many as 20 lawmakers, with nary a leak until Boehner accidentally disclosed its existence to the larger world when a video of his remarks at a conservative think tank was put online in January.

Toiling to avoid the tag of “amnesty,” the group has tentatively settled on a plan that would require illegal immigrants to appear in federal court and plead guilty to breaking U.S. immigration law.

Illegal immigrants would be required to complete this step before embarking on a conditional pathway to citizenship that would take at least a decade. In fact, illegal immigrants would essentially be granted legal status when a federal judge sentences them to “probation” for illegally crossing the border.

The House working group is poised to unveil its proposal in May, although the issue of guest workers has become an unexpected sticking point after Republicans balked at an agreement between the U.S. Chamber of Commerce and the AFL-CIO, sources said.

‘Moral Compass of Our Conference’

Although Rep. Raúl R. Labrador of Idaho, a relative newcomer to Congress and the secretive immigration group, has received much of the attention as the conservative face of the group, House lawmakers and aides say Johnson’s reputation both as a conservative and a war hero could prove more influential.

“Mr. Speaker, it’s no exaggeration when I say I believe that Sam Johnson is the moral compass of our conference,” Majority Leader Eric Cantor said on the House floor in February, marking the 40th anniversary of Johnson’s release as a prisoner of war.

Johnson’s Vietnam experience is the stuff of legend and he remains deeply affected by it. For example, he still refuses to eat rice.

Keith Self, a judge in Collin County, Texas, whom some Republicans consider a leading candidate to replace Johnson if he ever retires, recalled an outdoor political event where he was sitting next to Johnson on stage on a “bitterly cold” day.

The two hadn’t had a chance to say hello, so Self looked over to Johnson expecting a greeting. “And he says, in his Air Force colonel’s voice, ‘You are not supposed to shiver.’ It wasn’t, ‘Hello, Keith,’ it wasn’t — there was nothing. It was, ‘You are not supposed to shiver,’ and what he was telling me was, ‘You’re showing weakness,’” Self said.

POW Turned Key Salesman

Johnson’s status as a war hero also means he’s politically impervious at home. Though tea party activists in his district were shocked to learn that he was negotiating with Becerra and Gutierrez, it doesn’t mean they can do anything about it.

“I liken filing against Sam Johnson in a primary as serving roasted puppies at a PETA convention. It’s just, politically, the biggest violation of etiquette,” said Michael Openshaw, a conservative activist in Plano, Texas. Even so, “someone” did talk about mounting such a challenge in the last cycle, but Openshaw warned them “you cannot attack an M1 tank with a can opener.”

When Openshaw asked Dave Heil, Johnson’s chief of staff, to explain what the Texas Republican was up to, Heil responded in an email.

“In Sam’s view, sitting around and doing nothing is a great disservice to his constituency, his state and his country. He doesn’t want to be having this debate in another 10 or 15 years, we need to solve this problem now and for the future,” Heil wrote.

Supporters of the immigration group also think Johnson’s reputation will help sell their bipartisan deal.

“He’s a great American. Everyone loves him and he can do whatever he wants. If a POW of seven years is behind something, you’re just an asshole if you oppose it,” a GOP House aide said.

Maybe, although prudence would dictate some caution. Just ask McCain.