Bangladesh, trailing by 225 runs after the first innings, had resumed on 41 for two but soon lost Rajin Saleh (0) when he was caught behind off Vettori.
The left-arm spinner then ran through the Bangladesh order for his eighth five-wicket Test haul, finishing with figures of six for 28.
He was supported by Paul Wiseman who claimed three wickets, including the final one of tailender Mohammad Rafique who hit five fours in his innings of 24 before being caught by New Zealand captain Stephen Fleming.
Opener Nafees Iqbal had earlier offered some resistance until he was run out on 49 as only four Bangladesh batsmen reached double figures.
Bangladesh have lost 28 of their 31 Tests, drawing the other three. The second and final Test against New Zealand begins on October 26 in Chittagong.
New Zealand wicketkeeper Brendon McCullum had hit his highest Test score of 143 to help the tourists to a first innings total of 402.
Scorecard:
Bangladesh first innings 177 (Mohammad Ashraful 67; J.Franklin 5-28)
New Zealand first innings 402 (B.McCullum 143, M.Sinclair 76; M.Rafique 6-122)
Bangladesh second innings (overnight 41-2)
Nafees Iqbal run out 49
Javed Omar c McCullum b Vettori 14
Hannan Sarkar c & b Vettori 1
Rajin Saleh c McCullum b Vettori 0
Mohammad Ashraful c Styris b Vettori 26
Alok Kapali c McCullum b Wiseman 0
Khaled Mashud c Styris b Wiseman 2
Manjural Islam Rana c Richardson b Vettori 1
Mohammad Rafique c Fleming b Wiseman 24
Tareq Aziz lbw Vettori 0
Tapash Baisya not out 0
Extras (b-6 nb-3) 9
Total (all out, 54.5 overs) 126
Fall of wickets: 1-27, 2-33, 3-41, 4-87, 5-88, 6-92, 7-101, 8-112, 9-122
Bowling: Oram 7-4-6-0, Franklin 5-1-14-0 (nb-1), Butler 4-1-8-0, Vettori 22-13-28-6 (nb-2), Wiseman 16.5-1-64-3
Result: New Zealand beat Bangladesh by an innings and 99 runs.
Second Test in Chittagong from October 26.
