Medina komt uit de jeugdopleiding van Atlético Nacional, waarmee hij in 2011 zijn debuut maakte op het hoogste niveau. Een jaar later werd hij definitief bij het eerste elftal gehaald. In 2014 vertrok hij naar Mexico, waar hij tekende bij Monterrey. Na het seizoen 2014/15, waarin hij 35 wedstrijden speelde voor Monterrey, werd hij halverwege het volgende seizoen verhuurd aan Pachuca. Medina kan zowel als rechtsback als centrale verdediger spelen.
Medina speelde in diverse Colombiaanse nationale jeugdelftallen. In 2009 nam hij met Colombia –17 deel aan het wereldkampioenschap voetbal onder 17 in Nigeria, waar het elftal als vierde eindigde. Op 10 september 2013 debuteerde hij voor Colombia tegen Uruguay. Hij speelde de volledige wedstrijd, die Colombia met 2–0 verloor in Uruguay.[2] Op 11 oktober 2013 kwalificeerde Medina zich met Colombia in zijn tweede interland tegen Chili (3–3 gelijkspel) voor het wereldkampioenschap voetbal 2014 in Brazilië.[3]