One of the players he got in the deal was 22-year-old shortstop Jean Segura. Remember that name.
The Brewers were 14-7 in games started by Greinke, so he clearly was capable of pitching at a high level. Still, he was approaching free agency, and despite Melvin's best efforts, Greinke seemed inclined to walk.
Melvin held onto Prince Fielder a year earlier because he had a team capable of winning a championship. He looked at these 2012 Brewers and saw a team that was short in too many areas.
Twenty years from now, Melvin probably won't be able to understand what happened to his baseball team around that time.
All of a sudden, the Brewers were transformed from a bad team to a good one. Baseball people have no idea how or why this kind of thing happens.
Sometimes the pieces just fit together better than they had. Sometimes one player takes off and then another follows and another.
With the Brewers, it was a thousand little pieces. With Greinke gone, right-hander Yovani Gallardo stepped up and became a true No. 1 starter. Right-hander Marco Estrada kept churning out quality starts. Rookie Wily Peralta made the most of his opportunity.
All of a sudden, the Brewers couldn't lose. Thirty-three days later, they'd gone 23-6 and passed five of those six teams while cutting their deficit from 12 1/2 to 2 1/2 when they finished a 9-7 win Thursday in Pittsburgh.
The Brewers still face an uphill fight. The Cardinals lead by 2 1/2 games with 13 to play, so the Brewers have little margin for error.
Still, the Brewers made themselves relevant again. If you can clear that 54-66 start out of your head, they're a very, very solid club.
Whether they can close the deal is another matter. But the Brewers have done far more than save their season.
Here's what they are today. They're leading the NL in runs. They're No. 1 in scoring since the All-Star break and also tops in September. OK, there's that.
Ryan Braun has positioned himself to win a second straight NL Most Valuable Player Award by throwing a 40-home run, 105-RBI season on the board.
He's not a slam dunk, though, because Buster Posey has had a tremendous season for the Giants and also plays baseball's toughest position.
Still, if the Brewers somehow finish this improbable run to the playoffs, Braun probably will be the favorite to go back-to-back.
There's all kinds of offense around him. Rickie Weeks, Aramis Ramirez and Norichika Aoki have all had tremendous stretch runs as the Brewers have won 23 of 29 to spring back into contention.
Segura has settled in nicely as the starting shortstop, making every play -- some of them dazzling.
The Brewers can pitch, too. Even with the trade of Greinke and the shutdown of Mark Rogers, the Brewers can line up a rotation that's plenty good enough to carry them deep into October.
They've won each of Gallardo's past 10 starts, and since June 10, they're 16-3 in games started by Gallardo, Estrada and Peralta.
All right, there's that, too.
Peralta, 23, is an interesting one. He had a losing record and a 4.66 ERA in Triple-A. He walked 78 in 146 2/3 innings.
The Brewers just didn't know what they were getting when they were getting it. Peralta ironed out a flaw in his delivery, and in three starts, is 2-0 with a 1.80 ERA.
At the back of the bullpen, John Axford has made good on 11 straight save chances. Jim Henderson, Kameron Loe and Jose Veras have done good jobs getting the ball to him. Yes, there's all of that as well.
There's also Ron Roenicke. He's quiet and consistent. To keep a club headed in the right direction even after a terrible start says plenty about his leadership and the respect in which he's held by his players.
The bottom line is that the Brewers are a great franchise. They've averaged close to three million fans over the past five years, and owner Mark Attanasio has rewarded them by reinvesting in the club and focusing on winning a championship.
Few general managers are held in higher regard than Melvin, and now his club has a chance to make the playoffs for the third time in five seasons. All things considered, this surely wouldn't be the most satisfying journey of them all.