The third-wicket pair surpassed the previous best of 576 for the second wicket by fellow-Sri Lankans Sanath Jayasuriya and Roshan Mahanama against India at the Premadasa stadium here in 1997.
Skipper Jayawardene was unbeaten on 278 and Sangakkara was on 273 when they set the new record in the second over after lunch on the third day at the Sinhalese sports club on Saturday.
The record came through four byes conceded down the leg-side by wicket-keeper Mark Boucher off left-arm spinner Nicky Boje.
They had come to the crease on Thursday evening with Sri Lanka struggling at 14-2 in reply to South Africa's first-innings total of 169.
Both batsman have so far batted for over 10 hours in hot and humid weather in the Sri Lankan capital.
Jayawardene and Sangakkara were seven runs away from the record in the morning session.
The Sri Lankan captain was unbeaten on 276 with 31 boundaries and a six, having surpassed his previous best of 242 against India in the Asian Test championship match here in 1999.
Sangakkara was on 271 not out with 35 fours, overtaking the 270 he made against Zimbabwe in Bulayawo in 2003.
There was little the depleted South Africans, missing three top stars, could do to stop the rampaging Sri Lankans in good batting conditions.
The Proteas, already without the injured duo of skipper Graeme Smith and Jacques Kallis, also missed veteran all-rounder Shaun Pollock, who opted out of the match following the birth of his second child.
Pollock will be available for the second Test of the short two-match series which starts at the Sara stadium here on August 4.