Steyn's figures, the best by a quick at the Galle ground, helped the visitors bowl Sri Lanka out twice despite a wicket which offered little help.
It was only South Africa's third win on the island and their first since 2000.
Steyn was well-supported by seamer Morne Morkel, who picked up four wickets as Sri Lanka's second innings ended on 216 shortly into the second session.
The hosts needed to make another 260 runs on the final day with nine wickets in hand to pull off a come-from-behind win. But they lost their remaining wickets for just 106 to go down tamely in the end.
South Africa made 455-9 declared in their first innings before bowling out the home side for 292. In their second knock, South Africa declared at 206-6 to set Sri Lanka a target of 370.
The victory was especially sweet for Hashim Amla, who was leading the side for the first time in Test cricket.
He celebrated his winning start by hugging his teammates and exchanging high fives.
"It (winning) was not easy, credit to the boys, they put their hands up today," Amla said.
"We had some challenging overs last night but the bowlers came back and did really well. Dean (Elgar) got a hundred, JP (Duminy) got one as well and they set the game up for us."
South Africa, currently the world number two, can reclaim their top world ranking from Australia if they win the second and final Test in Colombo from July 24-28.
Part-time spinner Jean-Paul Duminy picked up two wickets including the crucial scalp of Kumar Sangakkara, who made a fighting 76 to salvage some pride for the hosts.
Sri Lanka, who had resumed on their overnight 110-1, added just 51 off 24 overs in the first session while losing five wickets.
"South Africans outplayed us on all the five days," said Sri Lankan skipper Angelo Mathews.
"We don't mind losing games if we have played good cricket but in this game we were really disappointing," he said.
"The first innings total (292) cost us the game, if we had added a bit more runs we could have been in with a chance. The batters need to improve their game."
Steyn, who had taken a five-wicket haul in the first innings, struck in the fourth over of the day to give his side the breakthrough they needed.
His victim was opener Kaushal Silva (38) who nicked the seamer behind the wickets, where Quinton de Kock dived to his right to take a stunning catch.
Silva's dismissal ended a 104-run stand with Sangakkara for the second wicket, the highest of the innings.
Sri Lanka were dealt a bigger blow off the first ball after the drinks break when Morkel had big-hitter Mahela Jayawardene caught behind for 10.
Sangakkara was dropped on 65 but failed to take advantage of the reprieve, pulling Duminy to short midwicket where Amla took a fine catch.
He hit nine fours and a six in his 145-ball innings.
The dismissal of Sangakkara and Jayawardene in quick succession infused new energy into the visitors.
Lahiru Thirimanne was caught by AB de Villiers off Steyn for 12, while Morkel had Dinesh Chandimal (one) caught behind by de Kock.
Sri Lanka lost Dilruwan Perera (zero) to Steyn in the second over of the post-lunch session, the tailender offering an edge to de Kock who took five catches in the innings.
Rangana Herath (20) was caught by de Villiers as he tried to play the sweep shot against Duminy.
Steyn, who was named man of the match, said it felt great to help his side win the game.
"Every time I come down to the sub-continent, I want to do well," he said.
"Nobody cares if you take five-for on a green top. But on a wicket like this, it really makes a difference."
COMMENTS
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ