Lewis missed three shots down the stretch and Padgett interfered with a potential tying 3-pointer by Stockton as the Jazz let a big opportunity slip away in an 89-86 loss to the top-seeded Sacramento Kings.
"We didn't expect such a tough game," Kings All-Star forward Chris Webber said.
After being swept by the Kings in the season series, the eighth-seeded Jazz were not given much of a chance in their Western Conference first-round series. Instead, they had plenty of chances but failed to capitalize.
"You can't find a lot of satisfaction when you lose," said Stockton, playing in his 174th playoff game, 10 more than Malone. "We had our chances, we didn't win, and that's that."
"This was a very important game for us," Jazz forward Donyell Marshall said. "Because if we could come out here and steal one, that would put a lot more pressure on them. We're probably the team in the Western Conference with the least pressure on them. We definitely felt we let one slip away."
Malone scored 13 of his 25 points in the fourth quarter, including a pair of free throws that cut the deficit to 88-86 with 48 seconds left. The Jazz stopped the Kings, but Lewis missed an open 3-pointer from the right corner.
The rebound was tapped into the backcourt and run down by Stockton. The all-time leader in assists and steals quickly dribbled upcourt and pulled up for a 3-pointer that rimmed out.
Webber rebounded and was fouled with 7.6 seconds to go. He missed the second foul shot, giving the Jazz one more chance. Padgett had a 3-pointer blocked and the ball went to Stockton, whose 3-pointer from the right wing hit the back rim and bounced straight up.
Instead of waiting to see if the shot dropped, Padgett tried to hammer in the rebound and was called for offensive goaltending in the final second.
"At the time, I didn't think it was going in," Padgett said. "But when we saw the replay on the monitor, it may have. If I had to do it over, I'd let it go. But I had already made up my mind to try and dunk it and maybe we could get a quick foul with about a second to go."
"I thought the last three we took were going in," Malone said. "The one Quincy had, he had a good look. Stockton had a couple. I thought they were all going in."
Lewis and Padgett both were playing in their ninth playoff game. Ironically, they were part of a bench effort that helped the Jazz stay with the Kings for the first time this season. Lewis scored eight points and Padgett seven as Utah's reserves held a 41-11 advantage.
Malone pulled down nine rebounds. Stockton scored 10 points -- all in the second half -- and handed out 12 assists. They were the only Utah starters in double figures.
Webber had 24 points, 12 rebounds and seven assists for the Kings, who host Game Two of the best-of-five series on Tuesday. They survived a chippy game to improve to 37-5 at Arco Arena this season.
"The Jazz played really hard and they came at us," Kings coach Rick Adelman said. "We were fortunate that they missed those two at the end. We'll take the win and move on."
"I am glad that we got the first one," Kings forward Peja Stojakovic added. "The second one is going to be a lot easier. We are going to be much more confident and not so nervous."
Malone scored seven straight points early in the fourth quarter before a layup by Greg Ostertag gave Utah a 73-72 lead. That was the first of six lead changes in the final period.
A basket by Malone, two free throws by Stockton and two by Malone gave the Jazz an 80-78 edge with 5:47 to go. Doug Christie answered with a 3-pointer and fast-break layup for an 83-80 lead, but Stockton and Lewis hit jumpers.
A hook in traffic by Webber gave Sacramento the lead for good at 85-84 with 2:33 to play. Lewis missed a 3-pointer and Stojakovic made one for an 88-84 advantage with 1:58 remaining.
On Utah's next two possessions, Lewis missed a lane jumper and Donyell Marshall missed a transition layup.
"Man, I'm gonna have to talk to that ball because I had a good look and it felt good when I let it go. It just didn't fall," Lewis said. "I felt the same on John's shots."
Mike Bibby scored 20 points, Christie added 17 and Stojakovic 15 for the Kings, who shot 45 percent (29-of-64) from the field.
Marshall had 11 points and 10 boards for the Jazz, who shot under 40 percent (33-of-83) but stayed in it with a 45-38 edge on the glass that helped them to a 19-1 advantage in second-chance points.
In the third quarter, the Kings were 11-of-13 from the line, while the Jazz did not get there. Sacramento used a 17-4 run to open a 69-59 lead with 2:01 left before Lewis stopped the surge with Utah's only 3-pointer in nine attempts.
"We didn't know how we were supposed to play," Jazz coach Jerry Sloan said. "We just lost our concentration, and you can't do that against this team; they're too good."
The Kings jumped to huge early leads in all four regular-season games and threatened to do so again, making nine of their first 10 shots and racing to a 21-11 advantage with just under five minutes to go in the first quarter.
Stockton sat down, but backup point guard Rusty LaRue and Marshall spearheaded a rally by Utah's bench. The Jazz closed to 25-20 after one period and continued the surge, taking a 42-35 lead before Stockton sat with his third foul with 3:12 left in the second quarter.
Malone grudgingly went to the bench with 1:47 to go and Sacramento closed to 47-46 at halftime. Marshall scored 10 points and LaRue seven as the Jazz's bench totaled 31 points.