The 79-year-old longtime conservative firebrand from Oklahoma and the 39-year-old Indian-American physician from Detroit make an unlikely pair.

But there they were in early January, GOP Sen. James M. Inhofe and Rajiv Shah, the administrator of the U.S. Agency for International Development, on a dirt road in a remote part of southern Ethiopia.

And they were stuck.

The two men, along with several other Republican members of Congress and their entourages, were on their way back from a visit to a rural development program in the midst of a downpour, when their vehicle came to a halt. They unloaded and waded through the mud, struggling for nearly an hour to dislodge the vehicle — “anyone under the age of 70 has to push!” Shah remembers Inhofe joking.

Said Inhofe afterward, “There’s no one I’d rather walk through the mud with than Raj Shah.”

That Inhofe, the new ranking member of the Senate Armed Services Committee, and Shah have managed to forge such a strong relationship speaks to their shared passion for ending poverty in sub-Saharan Africa. It’s also a testament to Shah’s assiduous work courting support on Capitol Hill for his ambitious efforts to overhaul the sclerotic agency, which is widely viewed as wasteful and inefficient.

By reaching out to lawmakers from across the political spectrum, Shah is helping build a political constituency for a part of the budget — international development aid — that has generally lacked one.

So far, that has paid dividends, both for USAID’s bottom line and in coalescing support for some of the changes Shah is trying to make to the bureaucracy.

Lawmakers howl about military base closures in their states or cuts to local infrastructure investments, but terminating funds for vaccination programs overseas doesn’t normally inflame too many in Congress.

USAID and its allies are trying to change this.

In addition to making the rounds on Capitol Hill, Shah has made a push to engage lawmakers on their home turfs, even some traditionally unfriendly venues. In September he and South Carolina Sen. Lindsey Graham, ranking Republican of the Appropriations subcommittee that funds the State Department and USAID, appeared on a panel together at Clemson University’s Strom Thurmond Institute of Government and Public Affairs — named for the legendary Republican senator who repeatedly voted to slash foreign aid spending and withhold funding to the United Nations.

Graham, Thurmond’s successor, struck a far different tone.

“This is how you win a war,” he said of USAID’s partnership with Clemson to train National Guard soldiers for work on agriculture projects in Afghanistan.

The same month, Shah attended a forum on food security at Mississippi State University with Sen. Thad Cochran, R-Miss., the ranking member on the Appropriations Committee. The university is a leader in agricultural research, including several programs in partnership with USAID. Cochran is an active promoter of food production and agricultural interests in his state and overseas.

Shah has also appeared in Minneapolis with Democratic Reps. Nancy Pelosi of California and Keith Ellison of Minnesota to talk about the U.S. response to the famine in Somalia, and in Atlanta with Sen. Johnny Isakson, R-Ga., to give a USAID award to Coca-Cola Co.

Inhofe says Shah’s willingness to accompany him and his GOP colleagues on the trip to a project run by Project Mercy, a USAID grantee — something the senator has repeatedly visited and supported — illustrates the young USAID director’s zeal for helping the world’s desperately poor, an agenda that has long united progressives and religious conservatives.

“It really comes from the heart,” Inhofe said of Shah. “That’s why I love and appreciate the guy so much.”

But that’s not the only reason lawmakers, and Republicans in particular, have warmed to Shah.

Previously an officer at the Bill and Melinda Gates Foundation, Microsoft founder Bill Gates’ globally influential philanthropy, Shah has tried to bring private-sector-style rigor to USAID programs. That includes a new approach to evaluating and measuring program results and to partnerships and contracting, a focus of Hill critics.

“USAID has become so stereotyped about the way that they work, there’s all kinds of lobbyists and others lined up and on the take,” Inhofe said. It makes one wonder, he added, “how much of the stuff, the effort from the United States, is actually getting to poor people.”

Shah also has not hesitated to slash programs he doesn’t think are working or are not critical to USAID’s core mission.

The agency is now in the process of eliminating more than 300 programs to focus on countries and projects that are having the most effect on poverty reduction, food security and global health.

“Instead of walking into a bureaucracy that has been operating the same way for decades … he came in and is changing as much he can,” Inhofe said.

Part of that agenda, however, requires bolstering USAID’s staff with highly trained personnel — to better monitor contracts and programs, Shah says, and to return more expertise to the government rather than relying on outside contractors. Shah has so far convinced Congress to provide enough funding to recruit and hire approximately 1,100 new staff, but the agency is not ready to stop there, though it knows it will continue to be a fight.

In fiscal 2012, Congress appropriated $1.5 billion for USAID, about $200 million less than the administration’s request. But it could have been much lower. House Republicans proposed only $900 million in funding for the agency in their budget. It fell to the Senate, both Democrats and Republicans, to fight to keep the cuts to a minimum.

Shah insists that his outreach to Capitol Hill is about more than just money. “No matter where you are on the political spectrum … we as USAID can learn from everyone as to how to do this work better and more efficiently,” he said.

But, with another stopgap funding measure and budget year looming, he also acknowledged that the tough fiscal environment continues to present challenges for his agency in Congress.

“I know that I have to continue to make the case all the time and on a case-by-case basis,” Shah said. “I find myself having to, wanting to … communicate the value that we generate.”