Title fights against Nelson

On September 10, 1993, Leija participated at one of the Alamodome's first ever events, when he challenged Azumah Nelson for the WBC super featherweight title. After twelve rounds, Nelson had been announced as the winner by a split decision, only to find out twenty minutes later that a judge had miscalculated his scoring card, and the fight was really a draw.

On May 7, he got a rematch with Nelson. Leija became the WBC super featherweight champion when he defeated Nelson by a twelve-round unanimous decision in Las Vegas.

Losing the title and afterwards

On September 17, he defended his title against Gabriel Ruelas, once again, in Las Vegas. Leija lost his world title when he lost to Ruelas by a twelve-round unanimous decision.

Leija rebounded with two wins, including one over Jeff Mayweather, and then, on December 15, 1995, he received a chance at becoming world champion for the second time, when he challenged Oscar De La Hoya for De La Hoya's WBO lightweight title, at Madison Square Garden. He lost by second-round knockout.

On June 1, 1996, Leija challenged Nelson, who had regained the WBC super featherweight title. Leija lost by a tech. knockout in six.

After a string of wins against relatively insignificant competition, Leija won the NABF lightweight title, defeating Joel Perez by a decision in twelve rounds on January 20, 1998.

After a second-round knockout victory over Troy Crain, Leija fought Nelson for the fourth time. In what was supposed to be Nelson's final career bout, Leija defeated Nelson by a twelve-round unanimous decision on July 11, 1998 (Nelson would later have a one-fight comeback against Jeff Fenech).

On November 14, Leija had a shot at the IBF lightweight title when he faced Shane Mosley. Leija was dropped in rounds six, eight and nine before the fight was stopped, with Mosley retaining the world title by a ninth-round knockout win.

Leija's next significant bout came on August 5, 2000, when he fought Juan Lazcano. Although no world championship was involved in this bout, it created general interest among Hispanic boxing fans, as Lazcano, nicknamed "The Hispanic Causing Panic," had become a popular boxer among Latinos. Leija lost an unpopular dec. in a ten-round split decision (scores of 94–96, 93-97 and a favorable 96-94) to Lazcano in Uncasville, Connecticut.

Next followed another HBO televised fight, when Leija fought Ivan Robinson, who had twice beaten Arturo Gatti, on November 11 at Las Vegas. Leija beat Robinson by a ten-round unanimous decision.

After a victory over Fred Ladd, Leija faced Hector Camacho Jr. in Long Island, July 7, 2001. This would prove to be a very controversial fight: after an accidental headbutt, Camacho Jr. was injured and he could not fight on. Camacho Jr. was initially announced as the winner by a technical decision, but the Leija team formally protested the result with the New York State Athletic Commission. The athletic commission decided to declare the fight a five-round no contest.

Micky Ward was being considered for a fight with WBC, WBA and IBF world light welterweight champion Kostya Tszyu. On January 5, 2002, Leija and Ward faced off at San Antonio. Once again, the fight was stopped as a consequence of a headbutt, but this time, it was Leija who was injured. Leija won the fight by a five-round technical decision, and became the number-one challenger to Tszyu.

Leija then proceeded to move to Australia for six months, to get acquainted with the country and its climate before his challenge of Tszyu, scheduled for January 19, 2003. Tszyu retained the title when he beat Leija by a six-round knockout.

After three wins, Leija faced young prospect Francisco Bojado. Leija and Bojado fought on July 24, 2004, in Atlantic City. Leija produced what some viewed as a minor upset by beating his much younger rival by a ten-round split decision.

Final bout

On January 29, 2005, Leija fought Arturo Gatti for Gatti's WBC light welterweight title. Fighting once again in Atlantic City, Leija lost to Gatti by a fifth-round knockout. Leija retired after the loss.