But thanks to a momentum-changing returns by Dante Hall and a vastly-improved defense turning downright stingy in the second half, Kansas City improved to 2-0 for the first time since 1996.
The reversal of fortune was enough to make a grown man, head coach Dick Vermeil, cry.
"I think we came back from some real adversity against a real good football team," Vermeil said. "No one's going to put us on top, but I think we took a giant step today, in some ways the hard way."
It was the first interception returned for a touchdown against Kansas City since Scott went 62 yards in Arrowhead in 2001.
The Steelers went up 10-0 on a Jeff Reed 20-yard field goal less than five minutes later, leaving Vermeil and the Chiefs with a sinking feeling.
"Everything you strive to do early in the game, we did just the opposite," Vermeil said. "But it's great to be able to do the opposite and recover from it."
Hall, sensing the need to give Kansas City a lift, took Reed's ensuing kickoff at the goal line and went nearly untouched 100 yards to immediately cut the lead to three.
"Guys were coming up to me (on the sideline) saying that we needed a play," Hall said. "We knew once we broke the ice we would be OK. It was a different game after that. Those type of plays turn momentum."
"It's frustrating to start that way, especially the way I did," Green said. "Both interceptions set up 14 points for them."
The defense picked Green up, allowing only two field goals the rest of the way.
Maddox threw for 336 yards, but he was intercepted three times and sacked four times. The Steelers were forced to throw because their running game produced only 60 yards on 16 carries.
"We knew all we had to do was get the ball back in our offense's hands," defensive tackle Ryan Sims, who had his first two sacks of his career, said. "They were up 10 points and they wanted to run the ball at us. We had to step up to stop them."
Woods had his first career interception return for a touchdown late in the second quarter, taking a pass deflected by Antwaan Randle El 46 yards to put the Chiefs up 27-17.
Hall gave the Chiefs another boost early in the third quarter, returning a Josh Miller punt 45 yards to the Pittsburgh 7. Two plays later, Priest Holmes scored his second touchdown of the day, a 4-yard bounce to the outside, to give Kansas City a two-touchdown lead.
"Dante's inspirational," Vermeil said with tears welling up in his eyes. "He not only inspires his head coach, he inspires his teammates as well. It takes all 11 guys, but he's a special type of sparkplug."
Linebacker Shawn Barber effectively ended Pittsburgh's last gasp, intercepting Maddox two yards deep in the end zone on a third-and-goal from the Kansas City 5.
"I was trying to do too much," Maddox said. "They blitzed and I never saw the linebacker coming. I felt like we had to score a touchdown there."
Holmes' third touchdown, a 31-yard gallop in the fourth quarter, was icing on Kansas City's very big cake. Holmes finished with 122 yards on 26 carries.
"It's kind of crazy to think that things went that poorly and we were able to come out with a 21-point victory," Green said. "That just tells you how far we've come as a team. It was just a great team win."