After a slow start, Malik changed gears in style, smashing 128, hitting a total of 16 boundaries in his 126-ball knock to help Pakistan register their second successive victory in the tournament.
His 206-run partnership off 193 deliveries with Mohammad Yousuf, who hit a composed 87 from 88 deliveries, saw Pakistan change the course of the match completely in the middle overs and amass 302 for nine.
The Indian bowling failed to live upto expectations, with senior-most Harbhajan Singh the main culprit, giving away 71 runs in his ten overs for just one wicket. Ashish Nehra toiled, claiming four for 55 in his ten overs, and Ishant Sharma took two for 39.
Chasing 303 for victory, Gautam Gambhir gave India the early impetus, smashing a cracking 57 from 46 deliveries, but his run out saw Pakistan take control. Leg-spinner Shahid Afridi consolidated Pakistan's position with the wickets of Virat Kohli (16) and Mahendra Singh Dhoni (3) in successive overs.
Raina then took charge with a blazing innings of 46 from 41 deliveries before he was trapped leg before wicket by Saeed Ajmal. He added 72 runs in 67 deliveries for the fifth wicket with Rahul Dravid, who was looking solid on 55 from 83 deliveries.
Left-armer Mohammad Aamer give Pakistan an early boost when he claimed the wicket of India's batting mainstay Tendulkar. The veteran batsman, who made eight from 14 deliveries, had no answers to an outswinging delivery from Aamer that clipped the edge of his bat to wicketkeeper Kamran Akmal. (23-1, 4.1)
Gautam Gambhir, back in action after missing the tri-series in Sri Lanka, looked positive as he hit two boundaries for 13. The left-hander made sure India's asking run rate was always in control as he looked to fetch a boundary every over as India tried to make sure that Tendulkar's early dismissal didn't affect their run chase.
The Delhi left-hander then launched into Aamer in the ninth over with a boundary and a huge six over midwicket as India made a strong start, reaching 65 for one after ten overs.
Gambhir completed his half-century in style from just 36 deliveries with a huge six over midwicket off a free hit from Umar Gul in the 11th over of the innings. Gul's first over fetched 16 runs as India raced to 81 for one after 11 overs.
With the seamers looking helpless against Gambhir, off-spinner Saeed Ajmal was introduced in the 13th over and he started off with just a single in his first over.
Just when things were looking good for India, Pakistan struck against the run of play with the wicket of Gambhir after a magnificent knock of 57 from 46 deliveries, inclusive of seven boundaries and two sixes. The left-hander attempted to steal a quick single but was sent back by Dravid and Younis found him short at the non-striker's end with a direct hit. (90-2, 13.5)
Gambhir dominated the second wicket partnership with Dravid as the two batsmen added 67 runs with Dravid scoring just 13 of them.
The Gambhir dismissal seemed to have tilted the scale slightly in Pakistan's favour as India were reduced to 97 for two after 15 overs.
Virat Kohli got into the act right from the outset with some good running between the wickets and it seemed he and Dravid looked set for a big knock. But a rush of blood cost Kohli his wicket as he attempted to take the attack to Afridi. Kohli, who made 16 from 24 deliveries, lofted one straight to Gul at long-off who held on after juggling it a couple of times. (126-3, 21.3)
Captain Mahendra Singh Dhoni found the going tough against the spinners and it was not long before he took the long walk back to the pavilion. Dhoni danced down the wicket to Afridi but missed his attempted flick to the leg side and was ruled leg before wicket by umpire Simon Taufel for 3. (133-4, 23.5)
Those two wickets by Afridi had given Pakistan the edge and it seemed virtually impossible for India to make a comeback with all their top batsmen back in the hut.
But India were not going down without a fight. It was Suresh Raina, who took the onus upon him as he smashed a boundary and six off Gul in the 29th over. He lifted Gul over point for his first boundary and then launched one straight down the ground for a huge six.
The young left-hander stepped down the wicket and creamed Afridi through the covers for his second boundary to take India to 178 for four after 30 overs. India were still in the contest, needing 129 runs from the last 20 overs with six wickets in hand.
Dravid completed his half-century off 74 deliveries, inclusive of three boundaries, with a single in the covers off Afridi in the 32nd over. Raina then brought up the 50-run partnership for the fourth wicket in 48 deliveries, with the left-hander having contributed 29 from 28 deliveries.
Raina was in no mood to relent as he carted part-timer Malik for two consecutive boundaries before unleashing a huge six over midwicket to race to 43 from 33 deliveries, with five boundaries and two sixes.
Just when it looked Raina would run away with the game, Saeed Ajmal trapped him leg before wicket with a quicker delivery. The left-hander walked back in disbelief suggesting to the umpire he had hit the ball first after a sizzling innings of 46 from just 41 deliveries, inclusive of five boundaries and two sixes. (205-5, 35)
Big-hitter Yusuf Pathan failed to deliver as he fell caught behind off Aamer for five in the 39th over. (218-6, 38.2)
Despite wickets falling from the other end, Dravid continued holding one end up with the odd boundary in between as India reached 229 for six after 40 overs, needing another 74 runs from the last 60 deliveries.
Dravid's brave resistance came to an unfortunate end when the veteran batsman was run out for 76. The right-hander relied mostly on rotating the strike, hitting just four boundaries in 103 deliveries, before Harbhajan Singh left him high and dry. (238-7, 42)
Naved-ul-Hasan ensured that the Indian tailenders didn't hang around for long as he claimed the wickets of RP Singh and Ishant Sharma in the 44th over. RP Singh lofted a slower delivery straight to Mohammad Yousuf at midwicket for 2 and two deliveries later Ishant Sharma's stumps were knocked down by a quick yorker.
Harbhajan tried the reverse sweep but failed to connect and was bowled for 133 as India were bowled out for 248 in 44.5 overs to lose by 54 runs.
In the end what made the difference was the bowling by the spinners in the middle overs. While India's spinners had struggled, Pakistan's spin duo had brought them back into the contest with Afridi and Ajmal claiming two for 39 and two for 31 respectively.
The victory virtually assures Pakistan's passage to the semi-finals stage, while India will need to beat Australia and West Indies in their last two matches to make sure of progressing to the last four.
PAKISTAN INNINGS:
Imran Nazir survived a run-out chance off the second ball of the match when Suresh Raina missed the stumps at the non-striker's end by a whisker as the right-hander attempted to steal a quick run on the off-side.
Nazir then made the Indians pay when he unleashed a cracking cover drive for his second boundary in the third over by Nehra followed by another couple boundaries off RP Singh in the fourth to race to 20 from 16 deliveries.
Just when it looked the Pakistan openers would run havoc, India struck back when Nehra claimed the vital wicket of Nazir. The right-hander, who made 20 from 17 deliveries, attempted a pull short but top edged it and was neatly held by Harbhajan Singh at mid-on. (29-1, 4.2)
RP Singh was taken off after just two overs, during which he gave away 21 runs, including four boundaries.
But Ishant Sharma fared no better as he also conceded two boundaries in his first over. Captain Younis Khan glanced the first one through fine leg for a boundary while the second was despatched through the cover region.
Akmal smashed Nehra through midwicket for his third boundary as Pakistan raced to 51 for one after just seven overs.
Once again India struck against the run of play when Kamran Akmal inside edged Nehra onto his stumps and was bowled for 19 from 22 deliveries. (53-2, 8.5)
Akmal's wicket saw the run-rate fall drastically as Pakistan cruising at 51 for one after seven overs managed only three runs in the next five overs to reach 54 for 2 after 12 overs. Ishant, who went for nine runs in his first over, had played a big role in the comeback as he gave away just a single in his next three overs including two maidens.
Meanwhile, RP Singh back for his second spell, came up with the important wicket of captain Younis for 20 (33b). The left-armer bowling from round the wicket got one to swing away from the batsman taking the edge to wicketkeeper Dhoni. (65-3, 14.4)
RP Singh made a strong comeback in his second spell, giving away just four runs in three overs and claiming the wicket of Younis.
Pakistan's innings looked stuck, as just 20 runs came from the last ten overs, with the scoreboard reading 71 for three after 17. Captain Mahendra Singh Dhoni took the opportunity to introduce his part-timers in Virat Kohli and Yusuf Pathan hoping to squeeze in a few tight overs.
The Kohli experiment lasted just three overs without much success as the youngster went for 21 runs, but at the other end Pathan was doing a good job with just seven runs from his three overs.
With the part-timers in operation, Mohammad Yousuf and Shoaib Malik had no problem getting their eye in as they steadily built the Pakistan innings in the middle overs as the duo brought up their 50-run partnership in 72 deliveries in the 27th over.
Yousuf then broke the sequence of singles with a delicate late cut through third man for a boundary against Pathan and Malik repeated that dose against Harbhajan in the next over.
The two batsmen finally decided to change gears as they slammed another two boundaries in Pathan's eighth over as he conceded 20 runs in his last two overs for 41 runs in eight overs. Those couple of boundaries also brought up the 100-run partnership between the two batsmen as they threatened to cut loose with the final few overs approaching.
Yousuf completed a deserved half-century with a single in the 35th over. The best part about his knock was that he kept it simple with singles and twos and despite hitting just three boundaries, brought up the landmark in 55 deliveries.
Malik completed his fifty in style off 81 deliveries when he slammed Ishant through point for his fifth boundary in the 36th over. He seemed to have changed gears after his fifty and slammed another two boundaries in the same over as Pakistan started to take charge.
Malik continued pounding the third man boundary as he thumped RP Singh for consecutive boundaries to race to 84 from 98 deliveries. Amazingly, the right-hander smashed 34 runs in his last 18 deliveries as the Indian bowlers looked totally clueless against the onslaught.
The last ten overs were a complete turnaround for Pakistan as they hit 83 runs to reach 217 for three after 40 overs.
Malik once again creamed Pathan through his favourite point region for his 12th boundary to move into the 90s. He brought up his century in 108 deliveries with another boundary when he cut Harbhajan through the third man region.
It was raining boundaries through the point and third man region as Yousuf drove RP Singh effortlessly for his fifth boundary.
Finally, Nehra gave his team some much needed relief when he claimed the important wicket of Yousuf. The veteran batsman tried to hit every ball out of the park in the PowerPlay but was beaten by the slower one and was bowled for a wonderful innings of 87 from 88 deliveries, inclusive of seven boundaries. (271-4, 46)
His 206-run partnership in just 193 deliveries for the fourth wicket with Malik had given Pakistan complete control after they were bogged down following the loss of a few wickets.
Shahid Afridi needed no time to warm-up and started with a lofted boundary over the cover region off Pathan in the 47th over. However, he fell off the very next delivery for 4, caught behind by Dhoni attempting another lofted over the off-side.(278-5, 47)
There was no stopping Malik, who, taking advantage of the fielding restriction, smashed successive boundaries off Nehra to start the 48th over.
But wickets kept falling from the other end when Umar Akmal perished caught behind by Dhoni for a first-ball duck attempting a big shot. (289-5, 47.5)
Nehra was easily India's best bowler of the day as he finished with respectable figures of four for 55 in ten overs, when all others around him were being carted all around the ground.
Malik's brilliant knock of 128 came to an end in the penultimate over when he holed out to long-on to give Harbhajan his first wicket. The Pakistan right-hander was in complete control, hitting 16 boundaries in his 126-ball knock to help his team post a huge score. Half of his runs came between the third man and point region as Malik fetched 61 runs from that area, having breached that boundary 12 times.
Harbhajan bagged a wicket off his final delivery but his figures read a miserable one for 71 in his ten overs, on a day when nothing worked for him.
Umar Gul tried a wild slog but ended up top edging to be taken by Suresh Raina at point off Ishant for a duck, while Mohammad Aamer hit a slower delivery straight to the mid-on fielder off the first delivery he faced.
Pakistan finished on a huge 302 for nine in their 50 overs leaving India with a tough task on hand in their opening encounter.
India eyeing revenge and title
Shoaib Malik eyeing romance with Sayali in a Bolly
Virat Kohli to replace injured Gambhir in Lanka
Team for WI: Nehra, Badrinath, Nayar in, Raina out
India to 'share' partial terror info with Pakistan