Hafeez (80 not out) and debutant Shehzad (55) added 101 runs for the second wicket to take their team to safety after Sri Lanka paceman Suranga Lakmal dismissed opener Khurram Manzoor (eight) early.
Pakistan reached 158 for two wickets when both teams agreed to a draw with first-innings centurion Younis Khan (13 not out) the other unbeaten batsman at the crease.
Lakmal troubled Manzoor on numerous occasions with his outswingers before finding his edge for wicketkeeper Prasanna Jayawardene to complete the catch as Pakistan chased 302 for an improbable victory in just over two sessions.
Shehzad was out leg before to Rangana Herath at the start of the final session and his attempt to overturn the umpire's decision through a review also proved unsuccessful.
But the dismissal came a bit too late for Sri Lanka as both their spinners and fast bowlers failed to make any significant impact on a docile pitch.
Earlier, Sri Lanka declared their second innings on 480 for five wickets after batting for 90 minutes in the morning session to add 60 runs to their overnight score.
Captain Angelo Mathews remained unbeaten on 157, his highest Test score, while Jayawardene was not out on 63. The duo added 156 runs for the unbroken sixth wicket.
The second of the three-Test series will be played in Dubai from Wednesday.
Scorecard
Sri Lanka first innings 204
Pakistan first innings 383
Sri Lanka second innings (overnight 420-5)
D. Karunaratne b Junaid 24
K. Silva c Akmal b Junaid 81
K. Sangakkara c Younus b Bhatti 55
M. Jayawardene c Shafiq b Bhatti 0
D. Chandimal c Rahat b Junaid 89
A. Mathews not out 157
P. Jayawardene not out 63
Extras (b-4, lb-7) 11
Total (five wickets dec; 168.3 overs) 480
Fall of wickets: 1-47, 2-146, 3-150, 4-186, 5-324
Bowling: Junaid 36-3-93-3, Rahat 38.3-9-92-0, Bhatti 36-8-146-2, Ajmal 49-10-115-0, Hafeez 9-1-23-0
Pakistan second innings
Khurram Manzoor c P. Jayawardene b Lakmal 8
Ahmed Shehzad lbw b Herath 55
Mohammad Hafeez not out 80
Younis Khan not out 13
Extras (lb-1, nb-1) 2
Total (two wickets; 52 overs) 158
Fall of wickets: 1-24, 2-125
Bowling: Lakmal 13-1-43-1, Eranga 11-0-38-0 (1nb), Herath 21-8-37-1, Mathews 2-0-9-0, Senanayake 5-0-30-0.
Image: Mohammad Hafeez
Photograph: Gareth Copley/Getty Images
Younis, Misbah hundreds put Pakistan in control
Pakistan's Junaid, Bhatti restrict Sri Lanka to 204
Sri Lanka recall Jayawardene, Herath for Pakistan Tests
Pakistan toil as Mathews ton gives Sri Lanka solid lead
Kohli retains number sixth position in ODI rankings