The Public Accounts of Canada show that between 2006 and 2011, his wife Laureen Harper â€” and for many years his personal stylist Michelle Muntean â€” were the most common add-ons to the government tab.
Then came the China trip last February.
The delegation to three Chinese cities included 30 executives from major oil, agricultural and manufacturing companies as well as roughly two dozen members of the Chinese-Canadian cultural community.
Compare that with a 2009 trip to China â€” Harper's first â€” when he brought along eight people, including Laureen, his stylist and four Chinese-Canadian businesspeople.
The Foreign Affairs Department says local transportation, accommodation, meals and "miscellaneous expenses" incurred by an official delegation is covered by the government. For the 2012 non-governmental participants, that meant an average of $1,200 a person.
Corporations and associations â€” including Bombardier, Cenovus Energy, the Canadian Association of Petroleum Producers and Cameco â€” confirmed that the government paid for portions of the expenses, with the amount varying from firm to firm.
"We'll leave it to the government to confirm those expenses. We won't comment any further on that," Isabelle Rondeau, director of communications at Bombardier, said of CEO Pierre Beaudoin's participation.
Rondeau pointed to German Chancellor Angela Merkel, who regularly travels with top businesspeople, including last year when she came to Canada.
"It's important that we have a very aggressive or very dynamic economic diplomacy. Why? Everybody does it. Many countries support their own business community, they organize these types of missions."
Barry Glotman, president and CEO of animal-rendering firm West Coast Reduction, said he spent most of his time with Agriculture Minister Gerry Ritz meeting Chinese business leaders.
"I was hesitant to go because I'm not one of these type of guys that are much into the politics, but after coming back I was more than impressed with the trip," said Glotman, who estimates he paid 90 per cent of his own expenses.
"I thought that it was really important in going over there. ... They assembled a lot of Chinese businesspeople, there were many people you could meet, and by bringing Canadian business guys along with the politicians it just adds that extra value than just the ministers going on their own."
The Canadian Taxpayers Federation says it doesn't see the rationale for paying any of the CEOs' expenses.
"I think most Canadians would be scandalized to learn that they're paying the expenses of a CEO of a large corporation to promote their company on a junket like this," said Gregory Thomas, federal director of the federation.
"It is very probable that had these same people been offered the opportunity to accompany the prime minister on a trade mission to China, they would cheerfully have attended and paid their own expenses."
Some of those companies, including gold company Eldorado Gold Corp., said they insisted on paying their own way throughout the trip and are surprised to hear they appear on a government expense list.
"Our CEO Paul Wright paid ALL his expenses (meals, cab fares, accommodations and any other expenses ) incurred on the trip," Nancy Woo, vice-president of investor relations, wrote in an email.
"We, too, would find it an unreasonable expense for the taxpayer."
Financial giant Manulife said it was their corporate policy to reimburse the government for any major expenses incurred by its executives, and is addressing the matter.
"Manulife covered Mr. Sterling's transportation expenses and is reimbursing the government for hotel costs, in accordance with our policy," said Laurie Lupton, assistant vice-president of corporate communications.
Carl Vallee, a Harper spokesman, cites a long list of agreements the prime minister signed while in China â€” including deals smoothing Canadian exports of uranium and beef tallow, and progress on a Foreign Investment Promotion and Protection Agreement.
Four of the firms in the delegation also signed commercial agreements with Chinese companies.
"This is standard Government of Canada practice," said Vallee, noting that travel to and from China was not covered.
"We are proud of the results the prime minister and our delegation have achieved during this trip."
Big delegations were indeed standard practice during the Liberal government years of Prime Minister Jean Chretien. He led eight massive "Team Canada" missions to Asia, Europe, the United States and Latin America that included both CEOs and provincial premiers.
A government official who spoke on condition of anonymity recalled that CEOs on those trips paid all of their own expenses, apart from meals at the daily receptions hosted by the government.
That style of trip fell out of vogue when Chretien left politics, and Liberal prime minister Paul Martin took power.
"Team Canada is a different approach," Martin told reporters in 2005 during a trip to China. "Team Canada was totally focused on transactions."
Harper also seemed unenthusiastic about the shock-and-awe style of trade delegation.
Former Conservative trade minister Stockwell Day says it appears the current government is now warming up to the concept, but using it in a more directed and thoughtful way by focusing on certain sectors.
"When you're talking about Asia ... any investment in Canadian companies and their opportunities over there is, I think, worthwhile," said Day, who has been doing consulting work in the region.
"As we know, and I think as the government increasingly realizes, so many of these Asian countries, especially China, put a lot of weight on the association between businesses and government."
NDP natural resources critic Peter Julian says it's fine to bring along businesspeople on a trade-focused trip, but not to pay any part of their bills.
"I think when hardworking taxpayers are seeing services being cut that they depend on, it's very difficult for those same taxpayers to swallow the fact that some of Canada's wealthiest and most profitable corporations are getting a subsidy from the Harper government," said Julian.
Members of the parliamentary press gallery who travel with Harper abroad are billed for their travel expenses. The Privy Council Office charged The Canadian Press $4,607 each for a reporter and photographer, for example, including $1,764 each for the flight to and from China in February 2012.