A 1992 graduate of Escondido High School in California, he played baseball and football before attending The Master's College in Santa Clarita, California for one year and then transferring to the University of Oklahoma.
In his sophomore year at Oklahoma, Redman set school records for strikeouts (136) and innings pitched (135.1) during the regular season and posted a 5-0 record in post-season play as he helped the Sooners win the 1994 College World Series title.
Redman named 1st Team All-Big Eight, Big Eight Newcomer of the Year, NCAA All-Regional team and was a member of the College World Series All-Tournament team in 1994. In addition, he was selected as a 1st Team All-American in both of his seasons at Oklahoma.
Redman was selected by Detroit Tigers in 41st Round (1148th overall) of the 1992 amateur draft, but did not sign with the team. He would get drafted again in 1995 by the Minnesota Twins in 1st Round (13th overall) and would make his debut with the team on July 24, 1999. Redman was later a member of the 2003 World Series champion Florida Marlins, contributing 14 wins to the team.
Redman was chosen to play for the American League in the 2006 Major League Baseball All-Star Game as the lone representative of the Kansas City Royals. He would finish the season with a team high 11 wins.
On March 9, 2007, he signed a minor league deal with the Atlanta Braves. On March 26, 2007, the Braves purchased Redman's contract from Triple-A Richmond. In his debut season with the Atlanta Braves, Redman pitched in 3 of the 5 initial losses for the team. His ERA was recorded as 8.62 on April 21, 2007. He continued to struggle with his ERA increasing to 11.63.
The Braves released him on May 22, 2007 and he signed a minor league deal with the Texas Rangers on May 29, 2007. Shortly thereafter, Redman requested his release from the Rangers and was granted it. Later, the Toronto Blue Jays signed Redman to a minor league contract on July 31, 2007. He was later released on August 16, 2007 after a poor start in Triple-A. He joined his fourth organization in 2007 when he signed a minor league contract with the Colorado Rockies on August 20. He was assigned to the Double-A Tulsa Drillers and made a start that same day. On August 25, he was promoted to their Triple-A affiliate, the Colorado Springs Sky Sox. On September 7, Mark Redman was promoted to the Rockies and made an emergency replacement after Elmer Dessens went down in the 2nd inning with a hamstring injury.
On December 13, 2007, he re-signed with the Rockies.
On April 26, 2008 at Dodger Stadium, Redman became the first MLB starter since 1900 to give up 10 or more runs in the first inning and still complete the inning, allowing 10 earned runs and managing to follow it with 5 scoreless innings before finishing for the day.