Hans ungdom er lite beskrevet, men han kommer inn i historien under sjuårskrigen (1563–70), da han var ved kong Fredrik IIs hoff, og ute i operasjoner. Etter krigen mottok han len i Danmark og Skåne. Fra 1579 var han landsdommer i Skåne; fra 1581 var han medlem av Riksrådet og i 1585 var han sammen med Valkendorf ansvarlig for riksstyret i kongens fravær.
Da Fredrik døde i 1588, og Christian IV ble innsatt som barnekonge, utnevntes Gyldenstjerne til stattholder i Norge og lensherre over Akershus. I løpet av hans tid som stattholder ble sorenskriverembetet opprettet, Akershus festning ble rustet opp, skattetrykket økte, grensene mot Sverige ble ettergått i nord, og Gyldenstjerne spilte personlig en rolle i å oppmuntre Peder Claussøn Friis til å oversette kongesagaene til norsk.
Gyldenstjerne fratrådte etter eget ønske i 1601, og mottok to len i Blekinge. Han deltok på en reise til Russland 1602–03, som ledsager for den danske kongens bror, prins Hans, som skulle giftes med tsar Boris Godunovs datter. Prinsen døde før bryllupet, og Gyldenstjerne døde selv under hjemreisen.
