It was ninth-ranked Canada's first tournament victory at their 140th attempt and came despite getting smashed by Fiji along the way.
"We beat three of the top five teams here so we're flying," said captain John Moonlight. "It's an unbelievable feeling, I'm so proud of the guys and how hard we've worked over the past year."
Canada won five of their six games, including a 26-14 win over New Zealand in the quarterfinals and then 17-5 over England, en route to the final. They led 19-0 in the final, before hanging on for a 26 - 19 victory.
Canada are coached by England's Damian McGrath, the former Samoa coach who was appointed in October and described the tournament win as "incredible".
Canada were beaten 35-7 by Fiji on the weekend, something they described as a turning point.
"We had a little bit of soul-searching, and then we came back and beat some of the best teams in the world," McGrath said. This will show that Canadian rugby has so much to offer."
Veteran Nathan Hirayama, his country's top sevens point scorer, told CBCSports: "A lot of us have been on the scene a while and we came through some dark times, but to come away with that win was special."
The team had been stripped of high performance funding, after failing to qualify for the Rio Olympics, but had been on a run of quarter-final appearances. Canada scored just their third win in 36 clashes against New Zealand, when they won the quarter-final.
The All Blacks Sevens beat South Africa 17-12 in the playoff for fifth.