A youth product of Nacional's academy, Medina played as a starter in the youth squad for one season before making his senior debut in 2011. Eventually, he gained a spot in the senior squad in 2012 after making occasional appearances. He was given the number 2 shirt in tribute to the late Andrés Escobar who also wore the same shirt, mostly because he's managed to avoid committing fouls as a defender by making good challenges. He has been liken to the late Nacional legend because of this. Medina finished his career with Nacional in 2014, winning 6 domestic trophies over the course of 4 seasons.
Monterrey
On 30 May 2014 the Mexican club Monterrey confirmed the signing of Stefan Medina for the fee of $4,200,000. He made his debut against Leones Negros, stating that while he was pleased with his debut, he still needed more time to fully adapt to Mexican football. He was a regular starter for the team throughout the entire 2014-15 season and was named in the team's starting lineup for the inaugural game at the BBVA Bancomer stadium, although throughout the Apertura 2015 his performance was frequently criticized and he was eventually benched by 18-year old rookie Cesar Montes in the centre-back position.
On 28 November 2015, Rayados de Monterrey announced that Medina had been transferred to Pachuca on a season-long deal, in exchange for Miguel Ángel Herrera. He made his debut for Pachuca on 9 January 2016 playing 90 minutes in a draw against Club Tijuana. He won the league title in May 2016 after Pachuca defeated his former club Monterrey 2-1 on aggregate, he was a starter throughout the entire season and was regularly deployed as a right-back, his loan was extended for the entire 2016-17 season during which he won the 2016-17 CONCACAF Champions League on April 2017 against Tigres UANL, playing as a substitute in both games at the Finals.
Return to Monterrey
On June 7, 2017 it was announced that his loan with Pachuca was terminated and he returned to Monterrey, with Cesar Montes, Nicolas Sanchez and Jose Maria Basanta all part of the center back position he was positioned in the right–back role. He was an integral part of the team as the starting right–back as they reached the finals of the Apertura 2017 league tournament losing to cross–town rivals Tigres UANL, and winning the Apertura 2017 cup against former team Pachuca. In 2019 with the arrival of Miguel Layún he was again moved to the centre-back position and excelled at the role, playing a vital role in the 2019 CONCACAF Champions League title win against Tigres UANL.
International career
Medina has been called up by the youth national squads on numerous occasions. In 2009, he was part of the team that finished fourth in the FIFA U-17 World Cup in Nigeria, appearing in two matches. He earned his first cap for Colombia on 10 September 2013 against Uruguay. Medina was regularly called on to the squad after his second cap, but suffered an ankle injury in April 24, 2014, thus forcing him to miss out on the 2014 FIFA World Cup. Medina wasn't called up for the squad again until early 2015, in a friendly against Bahrain and Kuwait, where he played in Colombia's 6-0 victory against Bahrain. In May 2018 he was named in Colombia's preliminary 35 man squad for the 2018 World Cup in Russia. However, he did not make the final cut to 23. He was included in the final cut of the 23-man list for the 2019 Copa America.
