Muralitharan finished with six for 87 to claim an impressive ninth five-wicket haul for the year, as Sri Lanka wrapped up the Test with four sessions to spare.
They had set New Zealand the improbable target of 504, but the home side had never batted with authority in the series and the outcome always seemed inevitable.
Despite a defiant eighth wicket stand by Daniel Vettori and James Franklin who put on 96, New Zealand were unable to cope with Muralitharan's mesmerising spin backed by Lasith Malinga's slingshot speed.
Their second innings ended at 286 shortly before the scheduled tea break on the fourth day.
But while the New Zealand batsmen failed to fire, Vettori providing their only half century, captain Stephen Fleming said full credit had to go to Sri Lanka's spectacular attack.
"The unorthodox nature of their attack was always going to pose a problem -- one of the greatest bowlers of all time and an action that's very hard to pick up makes it tough," he said on Monday.
After resuming the day at 75 for two, and still with an outside chance of reaching their target, Fleming and Mathew Sinclair staged a hopeful third-wicket partnership.
They were together for an hour and put on 55 runs, taking New Zealand's score to 115, before Malinga made the breakthrough.
With his first ball to Fleming he found the edge of the bat for Kumar Sangakkara to take a standard catch behind the stumps and the New Zealand captain was out for 27.
Muralitharan then struck for the first time of the day to take Sinclair for 37 and followed up by trapping Nathan Astle in front for nine and bowling Brendon McCullum for 17 to add to the dismissal of Craig Cumming at the start of the innings on Sunday.
At lunch New Zealand were 174 for seven after Chaminda Vaas completed the morning rout with the dismissal of Jacob Oram, and Sri Lanka could smell victory.
Vettori and Franklin staged their brave fightback through the middle session before Muralitharan had Vettori leg before wicket for 51.
Franklin was on 44 when he tried to bring up his half-century in one hit but a mighty swing at Muralitharan went straight to Chamara Silva at mid-wicket to end the innings.
It gave Muralitharan 10 wickets for the match for the fifth time in his last six Tests.
But the man of the match award went to Silva who overcame a double duck in the first Test to set up Sri Lanka's win in the second with a 61 in the first innings and 156 not out in the second.
The series now turns to limited over cricket with two Twenty20 matches before the first of five one-dayers on Dec 28.
Sri Lanka 268 and 365 beat New Zealand 130 and 286 (Vettori 51, James Franklin 44, Matthew Sinclair 37, Jamie How 33; Murali 6 for 87, Malinga 2 for 62) by 217 runs.