The following season was less successful, as the Mariners lost 99 games and Melvin's contract was not extended. He finished with a 156–168 record as Mariners manager. He returned to the Diamondbacks for whom he previously had been bench coach before being hired by the Mariners.
Melvin was fired as manager and replaced by A.J. Hinch, another former catcher, after the May 8, 2009 game. Melvin finished with a 337–340 regular season record and a 3–4 post–season record as Diamondbacks manager. Following the 2009 season, Melvin was a candidate to be the next manager of the Houston Astros. However, the position was filled by Brad Mills. He was interviewed by the Milwaukee Brewers for their managerial opening in October 2010, and was believed to be a finalist along with Bobby Valentine, Joey Cora and Ron Roenicke. The position eventually went to Angel bench coach, Roenicke. He was then interviewed by the New York Mets for their managerial opening before the 2011 season, but the position eventually was awarded to former Astros and Angels manager, Terry Collins.
In 2011, he was named interim manager of the Oakland Athletics on June 9, then on September 21, was promoted to manager of the A's, and agreed to a three-year contract extension after guiding the team to a 47–52 record (74–88 overall). Melvin went on the Chris Townsend Show in the Bay Area after the first game of the 2012 season in Tokyo, and promised the fans that the A's would work hard every game. He managed the A's to the franchise's best-ever record in July at 19–5. On October 1, the A's clinched their first playoff appearance since 2006, and two days later clinched the Western Division of the American League. The A's lost the 2012 ALDS (West Division) to the Detroit Tigers, three games to two. Melvin was honored as the 2012 American League Manager of the Year.
During the 2013 season, Melvin's second full season at the helm, the A's continued what began the previous year, posting winning records for every month of the season and securing a second consecutive AL West Division Championship. Employing numerous platoons, Athletics' outfielder Josh Reddick referred to Melvin as the "king of platoons".