Vesna Medenica je karijeru u pravosuđu započela u rodnom Kolašinu gdje je, nakon stručno-saradničkog angažmana, 1982. izabrana za sudiju Opštinskog suda. Potom je, u dva mandata, bila opštinska javna tužiteljka da bi, 1993. godine, napredovala u zvanje zamjenice višeg državnog tužioca u Podgorici.
Arhiva medija sadrži podatke o radu Medenice iz ranih 2000ih godina, kada je prisustvovala ispitivanju tada osumnjičenima za pokušaj atentata na srpskog političara Vuka Draškovića, koji se zbio u junu 2000. godine u Budvi. Medenica je potom proširila istragu i na članove Zemunskog klana, Mileta Lukovića i Dušana Spasojevića, koji su za pokušaj ubistva Draškovića bili osumnjičeni pored Ivana i Milana Lovrića i Vladimira Jovanovića. Luković i Spasojević tada su bili u bjekstvu, a optužnica nije podignuta do kraja te godine. „Zbog činjenice da u istrazi nijesu ispitani okrivljeni Dušan M. Spasojević (32) iz Zemuna i Mile Luković iz Beograda, jer su u bjekstvu, tužilac nije mogao da donese valjanu odluku“ - izjavila je tada Medenica.
Ona je nedugo potom izabrana za sudiju Višeg suda u Podgorici, a u martu 2002. godine njeno sudsko vijeće izreklo je kaznu zatvora od 20 godina za Željka Bulatovića, kome se sudilo u odsustvu, a zbog ubistva Samira Usenagića.
U julu 2003. godine izabrana je za državnog tužioca Crne Gore, i tu funkciju će uz velike turbulencije i optužbe obavljati u naredne četiri godine. Već do kraja te godine tražila je ostavku Zorana Piperovića, tada svog zamjenika i Zorana Radonjića, osnovnog državnog tužioca iz Podgorice, a sve zbog Piperovićevog navodnog učešća u aferi trgovine bijelim robljem, poznatoj kao „Moldavka S.Č“, i Radonjićevog postupanja u tom slučaju. Piperović je kasnije oslobođen ovih optužbi.
Početkom 2004. godine, u svom odgovoru Nebojši Medojeviću, tadašnjem lideru Grupe za promjene, navodi da je u javnosti kritikovani postupak privatizacije hotela „Avala“ i vile „Budva“ bio zakonit, „u svemu pravilno sproveden i da ne može biti poništen“. Prethodno je Grupa za promjene zatražila da državni tužilac ocijeni zakonitost i postupak te prodaje, navodeći da je "cijena od 3,2 miliona eura po kojoj je prodat hotel bila preniska, i da je Vladina konsultantska kuća Fleg procijenila tržišnu vrijednost hotela nekoliko puta veću od ostvarene".
U tom periodu navodno je tražila od italijanskih vlasti dokumentaciju o istrazi šverca cigareta koja se vodila u toj državi, a koja je uključivala Mila Đukanovića, tadašnjeg premijera i njegove bliske saradnike iz Crne Gore. Potom je, sredinom 2007. godine, tvrdila da sa italijanskim pravosudnim organima nije imala komunikaciju u vezi sa istragom šverca cigareta.
Nekadašnjem osnovnom državnom tužiocu u Kotoru a kasnije predsjedniku Višeg suda, Borisu Saviću, naložila je da istraži prodaju pola miliona kvadrata državnog zemljišta u Grblju kompaniji Olega Deripaske, za šta su optuženi kasnije pravosnažno oslobođeni.
Za vrijeme njenog mandata na poziciji vrhovnog državnog tužioca desila su se dva atentata koja nikada nisu do kraja rasvijetljena – ubistvo Duška Jovanovića, glavnog i odgovornog urednika „Dana“ i ubistvo Slavoljuba Šćekića, policijskog inspektora.
U novembru 2007. godine, neposredno prije nego što će biti izabrana za predsjednicu Vrhovnog suda, javnost je pozivala Medenicu da reaguje zbog dodjele posla izgradnje nove zgrade Uprave policije u Podgorici, koji je dodijeljen kompaniji „Čelebić“ bez raspisivanja tendera, kao i zaključenog posla o prodaji zemljišta istoj kompaniji. Ipak, Medenica će u svojstvu državnog tužioca krajem te godine poništiti ugovor kojim je Uprava policije prodala 7.637m2 kompaniji „Čelebić“ za oko tri miliona eura, „zato što je bio protivan imperativnim zakonskim propisima“, ali bez dalje istrage i ispitivanja krivično-pravne odgovonosti onih koji su zaključili ugovor, ali i bez poništenja posla o izgradnji nove zgrade Uprave policije.
Krajem 2007. godine započela je svoj prvi mandat na poziciji predsjednice Vrhovnog suda Crne Gore, i odmah potom od sudija tražila da do 1. maja završe sve istrage ratnih zločina, a da do 1. juna 2008. godine okončaju postupke koji se odnose na krivična djela iz oblasti korupcije i organizovanog kriminala.
U svojstvu predsjednice Vrhovnog suda nije trpjela kritike na rad sudstva čak ni kada su dolazile sa relevantnih međunarodnih adresa, a komentarisanje sudskih presuda od strane javnosti i medija smatrala je nedopustivim, tvrdeći da sudije rade po zakonu i savjesti. U tom kontekstu poznata je njena izjava:„Sudije imaju grešaka, ali te greške ne mogu da komentarišu novine, novinari, nekompetentni advokati i kvazipravnici“, kazala je Medenica u oktobru 2011. godine u Kolašinu osvrćući se na učestale kritike na rad pravosuđa, a tada konkretno na ukidanje presude osumnjičenima za ubistvo Slavoljuba Šćekića.
Kada je, početkom 2012. godine, opet izbila „Afera Telekom“, odnosno kada je u okviru istrage američkih državnih organa u vezi sa poslovanjem Mađar Telekoma objavljeno da su njihovi menadžeri za vrijeme privatizacije Crnogorskog Telekoma falsifikovali četiri ugovora, mediji su problematizovali postupanje Medenice za vrijeme obavljanja funkcije vrhovnog državnog tužioca, imajući u vidu da je tada promptno zaključila istragu i privatizaciju označila zakonitom. Ona je tada odgovorila da u ugovorima nije nađeno ništa sporno.
Sredinom 2014. godine ponovo se kandidovala za predsjednicu Vrhovnog suda, na koje mjesto je izabrana 26. jula, kao jedini kandidat. U narednim godinama učvrstila je rukovođenje pravosuđem, često oštro odgovarajući na kritike.
Početkom 2018. godine predsjedavala je vijećem sudija Vrhovnog suda koje je odbilo zahtjev Vrhovnog državnog tužilaštva za zaštitu zakonitosti u slučaju u kom su članovi porodice Kalić oslobođeni optužbi da su prali novac.
Već u aprilu 2019. godine, pred istek drugog mandata Medenice na čelu Vrhovnog suda, počela su javna govorkanja da nema prepreka da ona bude izabrana i na treći mandat, uprkos jasnim ustavnim ograničenjima, i to zato što je u međuvremenu donesen Zakon o sudskom savjetu pa se prvi Medeničin mandat ne može računati. Stoga, u junu te godine, objavljuje se da je Medenica jedini kandidat za tu poziciju, i Sudski savjet je u julu opet bira za predsjednicu Vrhovnog suda.
U tom periodu donosi i načelni pravni stav, po kome se odluke Skupštine Crne Gore o izboru, imenovanju ili razrješenju javnog funkcionera ne mogu pobijati (osporavati) u upravnom sporu niti u parničnom postupku, uz velike kritike stručne i laičke javnosti.
Nakon smjene vlasti u Crnoj Gori od 30. avgusta 2020. godine, i više poziva da podnese ostavku, Medenica istu najavljuje u oktobru 2020, a podnosi je krajem te godine i tom prilikom, između ostalog, izjavljuje: „Dozvolite da u tom pravcu izrazim visok stepen sumnje zbog sveukupnog društvenog konteksta, ali istovremeno i nadu da će vrijeme pokazati da je prestanak funkcije predsjednika Vrhovnog suda jedino nedostajao u ostvarivanju rezultata, koji će voditi mjerljivom napretku Crne Gore u pridruživanju Evropskoj uniji.“
Uhapšena je u aprilu 2022. godine na podgoričkom aerodromu, u okviru istrage koja se vodi protiv njenog sina Miloša Medenica, a zbog sumnje da je organizovao kriminalnu grupu čiji je ona bila dio, sa još više od deset osoba koji se terete za krijumčarenje, davanje i primanje mita, protivzakoniti i navođenje na protivzakoniti uticaj, neovlašćenu proizvodnju, držanje i stavljanje u promet opojnih droga... U optužnici Vesna Medenica se tereti da se od 2019. do 2021. godine obavezala da će korišćenjem položaja posredovati da se određeni predmeti pred Višim sudom i Vrhovnim sudom završe u korist privrednih društava "Fab Live" i "Cijevna Commerce", bez obzira na činjenično stanje.
Nakon što je u pritvoru provela pola godine, isti je napustila u novembru 2022, a suđenje u ovom predmetu počelo je ispočetka tek u februaru 2025. godine.