Nathan de Medina sloot zich op zevenjarige leeftijd aan bij de jeugd van RSC Anderlecht. In zowel het seizoen 2014/15 als 2015/16 bereikte De Medina met het elftal onder 19 jaar de halve finale van de UEFA Youth League. In april 2015 tekende hij zijn eerste profcontract bij de Brusselse club.[2]
Anderlecht
Op 19 mei 2016 maakte De Medina zijn officieel debuut voor Anderlecht. Hij mocht toen van coach Besnik Hasi in play-off I in de basis starten in de uitwedstrijd tegen KRC Genk. Anderlecht verloor het duel met 5–2. Ook in de slotwedstrijd van het seizoen, tegen Zulte Waregem, kreeg De Medina een basisplaats. Anderlecht won deze wedstrijd met 2-0. Onder Hasi's opvolger René Weiler belandde De Medina echter in de C-kern, waarop hij op 31 augustus 2016 werd uitgeleend aan Oud-Heverlee Leuven.
Excel Moeskroen
In augustus 2017 maakte De Medina definitief de overstap van Anderlecht naar Royal Excel Moeskroen.[3] In zijn eerste seizoen speelde hij negentien wedstrijden, maar in zijn tweede seizoen moest hij zich tevreden stellen met een halfuur speeltijd.
.svg){kind=small}
Excel Moeskroen
· 
· 
·
16 Mayoka-Tika ·
17 Dione ·
19 Vroman ·
20 Lucas ·
21 Gillekens ·
22 Bocat ·
24 Henry ·
25 Diandy ·
26 Silvestre ·
28 Angiulli ·
29 Badibanga ·
30 Carcela ·
32 Gnohéré ·
35 Mandanda ·
40 Simba ·
70 Tabekou ·
Myny ·
Giunta ·
Coach: Jeunechamps