After working out at the YMCA across from Busch Stadium during the 1958–59 offseason, Mizell showed a stronger fastball in 1959. He did not pitch at the beginning of spring training as he negotiated for a new contract, but he wound up settling for $17,000, his salary each of the previous two seasons. On May 15, he had a season-high 10 strikeouts, allowing just four hits and two unearned runs in an 8–2 victory over the Phillies. He had eight strikeouts in the second game of a doubleheader against Philadelphia on June 7, limiting the Phillies to five hits in a 2–0 shutout victory. In the first half of the season, he enjoyed a 9–3 record and a 3.05 ERA. He was named to both National League All-Star teams in 1959 (in those days, two All-Star games were played in a season). However, he did not appear in either game. The second half of the season saw him post a 4–7 record and a 5.94 ERA. On July 19, 1959, Mizell allowed three runs over seven innings to defeat the Braves, 9–5. He had to leave the game after the seventh with a pulled back muscle, but he was back in action four days later. He won just twice more all season, as he dealt with back problems. On August 1, he again struck out eight Phillies but received a no decision, as he was removed with one out in the ninth and the game tied 1–1. The Cardinals won on a Stan Musial home run in the bottom of the inning. In 31 games (30 starts), he had a 13–10 record, a 4.20 ERA, 108 strikeouts, and 89 walks in innings pitched.