For ti år siden slog hun massivt igennem med nummeret 'Kun for mig'.
Men Medina kan ikke selv huske det.
Hun har fået fortalt om tiden dengang, og hun kan se på billeder af de optrædener, der var med til at gøre hende danmarksberømt på ingen tid, men hun kan ikke selv genkalde sig starten af karrieren.
- Jeg fik en hjernerystelse lige, da min karriere startede, og jeg var syg i et år. Det er sgu mærkeligt altså, fortæller Medina, som har måttet få sin manager til at fortælle om episoder fra dengang, det for alvor startede, og 'Kun for mig' lynhurtigt både blev fast inventar på klubbernes dansegulv og teenageværelser landet over.
Her ti år efter er hun nu aktuel med sit første dansksprogede album siden 2011.
Efter flere engelske udgivelser – hen over sommeren har hun blandt andet hittet med 'First Time' sammen med det britisk-tyske producerteam M-22 – er hun tilbage med tekster på modersmålet på albummet 'Grim', der udkom fredag.
Medina kalder det selv et ekstremt ærligt album, hvor hun ikke bruger metaforer, som hun har gjort på sine tidligere sange, og faktisk er det lidt nervepirrende for den 35-årige sangerinde at blotte sig så meget, som hun føler, hun gør på det nye album.
- Det er ekstremt intimiderende, for nogle gange ser jeg mig selv sidde og skrive sange, som jeg ikke har lyst til at tale om, og så er det alligevel altid dem, der bliver til en single.
Lyt til det ti år gamle nummer 'Kun for mig' herunder, mens du læser videre:
Et helt særligt klubmiljø
Medina tager hatten af for sangskrivere, der kan sætte sig ned og skrive et hit efter en bestemt opskrift, men selv kan hun kun skrive om de ting og den musik, hun føler noget for.
Sådan er det nu, og sådan var det også dengang med 'Kun for mig'.
- Der var et helt særligt klubmiljø dengang, og musikken, der blev spillet, var så hård. København havde den her undergrund, hvor man malede sig hvid i ansigtet og tog mærkeligt tøj på, når man skulle ud. Det var så råt, og det var ud af det miljø, hele 'Velkommen til Medina'-pladen kom fra, fortæller Medina.
Hun lavede musik fra en mørk kælder med mug på væggene, og når hun tog ud med vennerne og veninderne, var det på de klubber, hvor folk klædte sig ud.
Den følelse af frihed brugte hun i sin musik.
- Det var en vild og fantastisk tid, fordi man bare så alle mulige forskellige typer i nattelivet. Det er sådan noget, der gør mig lykkelig, og det inspirerer mig så meget, når folk tør være sig selv. Der var mange, der kun kom for musikken, og musikken var kun for dem. Deraf 'Klubben fylder mine årer', siger Medina med en henvisning til første linje i 'Kun for mig'.
En følelse af at være grim
En fiskesnor spændt ud mellem to træer på Kongens Nytorv i København var tæt på at sætte en stopper for det hele.
Medina kom cyklende hen over pladsen, på vej til at mødes med en veninde, og hun kørte direkte ind i snoren, fløj tilbage og hamrede baghovedet ned i jorden.
Men den slemme hjernerystelse og de efterfølgende mén, som betyder, at hun i dag stadig har problemer med hukommelsen, lagde ikke en dæmper på Medinas vilje til at slå igennem. I 2009 spillede hun således over 200 koncerter alene i Danmark.
Dengang var det klubben, der fyldte hendes årer – nu er det en anden følelse, som Medina beskriver på det nye album 'Grim', der også indeholder en sang med samme titel.
Der er nogen, der har sagt, jeg er grim
Og jeg tror på dem
For jeg har mistet mig selv igen
Salt i mit sår
Der er nogen, der har sagt, jeg ikke er nem
Og jeg tror på dem
Sådan synger Medina på nummeret 'Grim'. I løbet af sine mange år i branchen har hun nemlig fundet ud af, at hun nok ikke rigtig passer ind i hele mediecirkusset, og det berører hende meget, når der bliver skrevet mindre positive ting om hende.
Lyt til sangen 'Grim' herunder:
- På et tidspunkt havde jeg lyst til at sige til hele verden, at nu stopper jeg, for jeg gider ikke det her fucking pis fra medierne mere. Jeg er så færdig med at stå til måls for alt det lort, andre har at lukket ud for at få kliks eller likes. De fik ramt mig, og jeg følte mig bare så grim til sidst.
Det samme team som for ti år siden
Hun fortæller, at hun er blevet hængt ud for ting, hvor hun ikke engang var i landet, og hun har oplevet, at en journalist bevidst puttede persille i tænderne for at finde ud af, om Medina ville sige noget.
- Det er mobning på et sindssygt niveau. Men jeg tror, der er mange, der kan nikke genkendende til det. Om det så er lille Karl, der bliver mobbet i klassen og får ar, han tager med sig resten af livet, eller om ens chef på arbejdspladsen er en kæmpe nar, siger Medina.
Men hvorfor så blive ved med at lave musik og leve i rampelyset, når det tit er for svært?
Medina vil ikke dvæle for meget ved fortiden, for hun kan ikke ændre noget nu, og så kommer hun igennem de hårde tider ved at have de bedste mennesker omkring sig, som hun selv beskriver det.
Hendes team er det samme som fra dengang i den mugne kælder, og hun får energi af at være ude at spille. Og så er der jo fansene.
- Der er over 100 mennesker i verden, der har tatoveret ting, jeg har sagt eller skrevet. Eller mit ansigt. Det er ret vildt. Det er bare ekstrem kærlighed, man får lov at se vokse, og det er smukt, siger Medina, som også selv følger med i fansene liv.
Nogle kan hun genkende, når de står oppe foran scenen til deres Medina-koncert nummer 100, og andre har hun set have kræft og senere blevet rask.
- Der er en kerne omkring mig, og den kan man bare ikke fucke med. Det er så vigtigt at have.