Scott Rolen's two-run home run off Hoffman followed by Joey Votto's walk-off single in the bottom of the ninth inning completed the Reds' late rally from a three-run deficit.
It was Hoffman's fifth blown save. He gave up three earned runs and four hits in the ninth and did not retire a batter, dropping his record to 1-3.
"I'm not getting outs," said Hoffman. "There's not a lot to analyze about it. It's pretty obvious that I'm not getting it done. If there was an answer at this point in time, we would've found it."
It was a victory the Brewers desperately needed, and one they seemingly had in hand.
But nothing is a certainty this season.
"You have to get 27 outs, not just 24," said Brewers manager Ken Macha. "We played a great game, got good pitching, then got to the ninth inning and didn't get anybody out. It's a tough part of the game when you play your heart out and can't close it out."
Until the ninth, the Brewers got what they were hoping for on Tuesday, and more.
Manny Parra enjoyed a successful season debut as a starter, allowing just one run and four hits in four innings. He walked four and fanned three in an 84-pitch effort.
Marco Estrada, who was recalled from Triple-A Nashville prior to the game, made his Brewers debut and pitched four innings in relief of Parra, giving up one run and two hits with no walks and four strikeouts.
"Estrada pitched his heart out," said Macha. "What a lift he gave us. We were looking for someone to step up in the bullpen. He picked us up. He was impressive."
Ryan Braun belted his seventh home run of the season on a 3-1 pitch from Reds starter Homer Bailey to put the Brewers ahead 1-0 in the first.
Prince Fielder doubled, and Casey McGehee followed with an RBI single to make the score 2-0.
McGehee went 3-for-4 with a double and two RBIs.
Jonny Gomes, who hit a game-clinching three-run homer off Todd Coffey on Monday night, doubled home Chris Heisey to make the score 2-1.
"They were really patient on some close pitches," said Parra. "I was surprised actually. I put a lot of good pitches on them. They were very selective. Maybe they have a better game plan now and that's why they're winning."
Estrada pitched two perfect innings then batted for himself with runners on first and third and two outs in the seventh, grounding out to short to end the inning.
He rolled through the seventh, retiring the Reds in order with two strikeouts.
"I was happy with my performance, but we lost," said Estrada. "I'm glad I gave the team a chance to win. I felt great. I had so much adrenaline going."
After a rocky first, Bailey pitched five straight hitless innings, allowing just two walks. He allowed two runs and four hits, walked two and struck out four in seven innings.
Carlos Fisher (1-1) earned his first victory of the season for Cincinnati.
McGehee added an RBI single, and Braun scored on a wild pitch to cap a two-run eighth, making the score 4-1.
Estrada's only blemish was a 460-foot home run by Votto leading off the eighth.
Votto's blast was just the eighth homer to clear the batters' eye in center field at Great American Ball Park since it opened in 2003.
"I let a couple pitches go, and they got hit," said Estrada, who tied career-highs for innings and strikeouts.
Votto went 3-for-5 with a home run and two RBIs.
Estrada was in line for his first Major League victory until the Reds erupted for three runs in the ninth off Hoffman.
Rolen's second career pinch-hit homer, on a 1-2 pitch from Hoffman, tied the score.
"He's the all-time saves leader, and I certainly don't look forward to facing him," said Rolen. "I've seen the ball fairly well off of him in the past. I saw the ball well today. Imagine my surprise when the thing went out."
Heisey doubled, and Brandon Phillips walked before Votto singled off the base of the right-field wall to score Heisey with the winning run.
"I asked [Hoffman] what I could do to help him," Macha said. "He said I was doing everything I could do. We'll sit down with [Brewers pitching coach] Rick [Peterson] and see what we can do. We'll work on a solution."