"We played great baseball the last three games," said Indians starter Carl Pavano, who allowed three runs in six innings and traded scoreless frames with Greinke in innings four, five and six.
Pavano exited with the Tribe trailing, 3-2, but the Indians' offense gave him the win with two runs in the top of the seventh.
Shin-Soo Choo tied the game at 3 with a two-out RBI single off reliever Horacio Ramirez, and Jhonny Peralta gave Cleveland a 4-3 lead with an RBI double over the head of KC right fielder Jose Guillen.
The Indians broke the game open with four runs in the eighth.
Asdrubal Cabrera, who led off each game of the series with a hit, lifted his average to .327, and Choo, who was 3-for-5, had three singles and raised his average to .303.
"Three hundred is special in the big leagues," said Choo, who was 6-for-12 in the series.
The offense pulled together for eight runs, and the bullpen pulled together to hold the lead.
Luis Vizcaino threw a scoreless seventh, Matt Herges shut down the Royals in the eighth, and Rafael Betancourt recorded three quick outs in the ninth after Herges loaded the bases with no outs. Betancourt retired David DeJesus on a foul pop up down the left-field line and then got Alberto Callaspo to bounce into a double play to end the game.
"Betancourt was about as efficient as you can be to get three outs there in the ninth," Indian manager Eric Wedge said.
The rest of his pitching staff was nearly as good.
"We really made [Greinke] work hard, and they made Carl work hard," Wedge said. "You got a couple of guys pitching well, and they're out of the game after the sixth inning. So it was left up to the bullpen, and our guys really stepped up down there. It should be a big boost for them."
Likewise for the rest of the Indians, who had won back-to-back games just once before Thursday and had yet to beat a team twice in a row.
After this, the Indians have plenty of reasons to feel confident.
First, they had to work past Greinke. They mounted their only charge against the Royals' ace in the third inning, putting up two runs on four hits. Luis Valbuena and Grady Sizemore started the rally with singles to right field, and Martinez and Choo added consecutive RBI singles to tie the game at 2. Peralta walked to load the bases, but Greinke struck out Mark DeRosa and Ben Francisco to limit the damage.
It was the first time Greinke, the American's League's ERA leader, had given up two earned runs in an inning this season.
"I think the difference was they took good approaches the whole game and made it a grind all game long," said Greinke, whose pitch count surpassed 100 after six innings.
The Indians also rebounded after the Royals took a 2-0 lead in the bottom of the first, and then put them away in the eighth when they got the chance. After a frustrating series in St. Petersburg and a painful loss against Kansas City on Tuesday, the Tribe can breathe a little easier.
"We just got to carry this into Cincinnati and keep it going," Pavano said.