And, we see now, it was true, he didn't need a majority. Maybe that's why he seems to be going slowly and cautiously with the one he has.
Canada has changed incrementally under Harper, a nudge here, a push there, and next thing you know we're sitting by the crab apple tree over in the corner of the yard instead of the front porch.
Well, that's a bit dramatic. He hasn't moved us physically, but it appears Canadians, more and more of them, may be looking at the world the way he does.
It came out, maybe, during that crazy Canada Day celebration in Ottawa when apparently, according to police and government officials, 300,000 people turned up near and on Parliament Hill to see the Duke and the Duchess of Cambridge, aka Prince William and Kate.
It is difficult to imagine the figure to be accurate, since Parliament Hill even in normal times does not have space for that many people and nearly half the Canada Day lawn was fenced off for the stage and the royal venue to the side. You can't even imagine that many people even if you stretch them out over the nearby streets, Sparks, Wellington, even to slightly distant Albert and Queen, royal sounding as they are.
It would be literally like taking the entire population of the city of Gatineau, across the river in Quebec, and plunking it down in the streets and precincts around Parliament Hill. It would be a crush.
But it was wild, watching and listening through various media from a safe distance as people camped overnight, lined up for hours, screamed like a rock audience and thrust their hands and flowers forward to get a touch.
Harper himself lit the crowd-estimate fireworks during his noontime Canada Day oratory.
"What a great crowd," he said. "I thought we had a big crowd last year, but I think this is the biggest yet."
Queen Elizabeth, the prince's grandmother, was there last year, same day, same time, but Harper was either suggesting this was the biggest in history, or the biggest he's seen since he took over.
So, though we'll see how it goes through the rest of the royal honeymoon, Canada seems to have reverted back in some ways to days past, back beyond the sixties, when royal tours weren't taken for granted, with grainy family photos showing people lined up even at little whistle-stops on the lonely Prairies, as the Queen and Prince Philip, roles in reverse from William and Kate, made their way across the country on a train.
It's eery in a sense. Harper was born in 1959, he was 10 years old when the peace movement was at its height in the U.S., really still nascent in Canada, where it crested in the very early 1970s.
That is well after first memory for Harper, he would have been watching it all, along with his father, from all appearances a conservative minded family man who spent his days as an Imperial Oil executive, also viewing the social upheaval.
That's about the time the government of Pierre Trudeau began slashing the military, shrinking it further and further as the doves flew and Canada set out on its peacekeeping journey, as far from Vietnam as it could go.
Which brings us to another way in which we see the way Harper has subtly, incrementally begun to change Canada. It is the way the country views itself in the world, more now as a nation of warriors again, after 10 years in Afghanistan, many soldiers having given up their lives in the fight against post-9/11 terrorists.
Now, in a smaller way, Libya, where even the NDP barely blinked as it unanimously voted to extend Canadian participation in the NATO bombing campaign against Moammar Gadhaffi.
That came out on Canada Day, too, as both Harper and William devoted many of their words to the military. William's first stop in Ottawa was the National War Memorial.
Canada has an "unbeatable" spirit, said Harper, calling it the spirit that led Canada out of the recession and "the spirit of the Canadian Armed Forces in Afghanistan, Libya, all around the world, the men and women of the Forces who so inspire us as Canadians."
True, Canada honours the bravery and professionalism its soldiers are famous for among other armed forces, and the sacrifices they have made over the past decade, but the theme of the military, and Canada's participations in past battles and wars, has been a constant undertone of the Harper government since it first won power in 2006, even earlier actually, when the Conservatives adopted their Stand Up For Canada slogan for the Conservative campaign in that election.
The Harper government singlehandedly made Vimy a household name in Canada.
And there's more on the way. The government used the Throne Speech last month to flag bicentennial celebrations it is planning for the War of 1812, when Canadian militia, first nations and farmers helped the British army stave off a U.S. invasion.
The Throne Speech, long ago it seems now, also pointed out the government will celebrate the 200th anniversary of the Selkirk Settlement, "which marks the founding of Manitoba and the early days of the modern West."
An earlier section of the speech made brief reference to the scars that remain from that settlement, more critically what happened afterward, saying "Canada's aboriginal peoples will be important to our future economic prosperity."
Aside from the crime bills, which themselves are a throwback to days past, the end of the long form census, the multi-billion-dollar injection into the military, a court battle even to close Vancouver's safe drug-injection clinic, there are many other ways Harper has been slowly changing Canada's face, as well as the views of its citizens.
And he hasn't really had need of a majority, so far.