1st Championship Reign

Medina won four bouts, then had his first chance at becoming a world champion, when, on August 12, 1991, he faced IBF featherweight champion Troy Dorsey in Inglewood. Medina was knocked down twice early, but became a world champion by getting up and defeating Dorsey by a twelve-round decision. He made four defenses of his title, including victories against Tom Johnson, beaten by a nine rounds technical decision and Fabrice Benichou, another world champion boxer, outpointed by Medina over twelve rounds. His first reign as world featherweight champion took him to places like France and Italy.

Medina lost the championship to Johnson by a twelve-round decision on their February 26, 1993 rematch, held in France. He turned to the super featherweight division, where he won one fight, then attempted to become world champion there also. But, on June 26 of the same year, he lost to IBF super featherweight champion John John Molina by a twelve-round decision, in Atlantic City.

2nd Championship Reign

Medina then returned to featherweight, where he won two more fights before facing Johnson in a rubber match, held on January 28, 1995 at Atlantic City. Johnson retained the IBF featherweight title he had won from Medina by beating him via a twelve-round decision. In his next fight, Medina won the WBC's regional Fecarbox title by defeating Juan Polo Perez by a twelve-round unanimous decision on March 15 in Miami, Florida.

Medina's next fight was televised nationally in the United States, as he became world Featherweight champion for the second time, defeating Alejandro González on September 23 of '95, with a twelve-round unanimous decision, at Sacramento, California, for the WBC featherweight title. He lost the title in his first defense, losing a twelve-round decision to Luisito Espinosa on December 11 at Tokyo, Japan.

After a win, Medina tried to become a three time world featherweight champion by challenging Naseem Hamed for Hamed's WBO title, but he was defeated by Hamed with an eleventh-round knockout on August 31, 1996 in Dublin, Ireland. He followed that loss with a win, and another attempt at winning a world featherweight championship for a third time, this time around in a rematch with Espinosa. held on May 17, 1997. He lost to the Asian champion, this time by an eight rounds technical decision at Intramuros, Philippines. Medina then lost his next fight, by a ninth-round knockout on August 7, to future world champion Derrick Gainer.

On October 18, he recovered from his two loss streak to defeat Jose Ayala in Homestead, Florida, winning the WBA's Fedecentro regional championship, and setting himself in a position to obtain another chance at winning the world featherweight title for the third time. He knocked Ayala out in the eighth round.

3rd Championship Reign

On April 24, 1998, Medina joined Carlos De León, Muhammad Ali, Sugar Ray Robinson, Edwin Rosario, Evander Holyfield and a small number of other boxers in the exclusive group of fighters to reign as world champions three or more times in the same division, when he outpointed defending IBF title holder Hector Lizarraga over twelve rounds in San Jose, California. He retained the title on April 16, 1999, in Las Vegas with a nine rounds technical decision over former world super featherweight champion Victor Polo, then proceeded to lose the championship to Paul Ingle.

The fight against Ingle, held on November 13 of the same year, in Hull, England, went on to be considered one of the fights of the year by boxing fans, experts and magazine writers alike. Floored in the second and tenth rounds, Medina almost saved his title when he dropped Ingle in the twelfth and last round. He ended up losing a unanimous decision, however.

Medina then met future world champion Frank Toledo, beating him in Las Vegas by a ten-round decision on May 19, 2000. Toledo then went on to win the IBF title by outpointing Mbulelo Botile, who had defeated Ingle. Medina, meanwhile, picked up two more wins, including a fourth-round knockout over future world title challenger Mike Juarez.

4th Championship Reign

Medina and Toledo had a rematch on November 16, 2001, with Medina joining Robinson as a four-time world champion in the same division when he knocked Toledo out in the sixth round.

His next fight was filled with controversy. Faced against former two division world champion Johnny Tapia on April 27, 2002, Medina lost the title by a twelve-round majority decision at the Madison Square Garden in New York City. The decision was criticized for months to come by writers from such publications as Ring and KO Magazine. The official scorecards reflected a very close fight, with two judges scoring it 115-113 for Tapia and a third scoring the fight a 114-114 tie.

Medina's first attempt at tying Robinson's record as the only boxer to win a world title in the same division five times came on February 1, 2003, when he and Juan Manuel Márquez faced off in Las Vegas for the IBF championship vacated by Tapia. Medina was knocked out in the seventh round by Marquez, however.

5th Championship Reign

After two more wins, Medina got his second chance at becoming world featherweight champion for the fifth time against WBO champion Scott Harrison. The two boxers fought for the first time on July 12 at the Braehead Arena in Glasgow, Scotland. Medina made history and joined Robinson as the only two fighters in history to be five-time world champions in the same division, by defeating Harrison, who until then had been defeated only once, by a twelve-round split decision. A boxing magazine from the United States then called Medina the gambler's nightmare, because of his tendency to win world featherweight titles, lose them quickly, then regain them just as quick.

Medina and Harrison were rematched on November 29 of the same year, and Harrison regained the WBO title with an eleventh-round knockout of Medina, again, at the Braehead Arena in Glasgow.

Super featherweight

Medina only fought once in 2004, defeating Leonardo Resendiz on July 23 at Rancho Mirage, California by a third-round knockout, to win the WBA's regional NABA super featherweight title.

He was to fight José Miguel Cotto on August 20, 2005 in Ponce, Puerto Rico. Had he beaten Cotto, he would have put himself in a position to challenge for the WBO super featherweight title. Cotto was not able to reduce weight to the super featherweight weight limit, however, so the fight was suspended.

On 31-05-2006 he fought Cassius Baloyi for the IBF super featherweight title, the same title he'd challenged Molina for back in 1993, and lost by 11th-round TKO.

Medina returned to outpoint Kevin Kelley by a twelve-round majority decision, then fought a rematch with Baloyi on 05-07-2007 which was scored a technical draw after Medina suffered a cut from an accidental clash of heads. In his final fight, Medina lost by a two-round TKO to Malcolm Klassen. These final three bouts were all IBF super featherweight Title Eliminators.

Medina has a record of 64 wins and 15 losses in 78 professional boxing bouts, with 30 wins by way of knockout.