After losing to Madrid, Medina had a streak of twenty seven wins in a row. That streak was stopped by Juan C. Salazar, who outpointed Medina over ten rounds on July 10, 1989, in Tijuana. After two more victories, however, Medina contended for his first championship belt, the regional WBA "International" super featherweight title, which he won by a seventh round disqualification victory against Edgar Castro, on December 11 of that same year, in Inglewood. Medina retained that title twice, then defeated Tyrone Jackson on May 21, 1990, also at Inglewood by a twelve-round decision. In his next fight on 5 July, he outpointed former world featherweight champion and Barry McGuigan conqueror, Steve Cruz over ten rounds.