I februar [[1596]] kom Gyldenstierne med sin hustru tilbage til Akershus fra et besøg i Danmark. Den lange slædetur fra [[Helsingborg]] til [[Oslo]] synes at have oversteget fruens kræfter; for kort efter blev hun syg og døde ([[8. marts]]). Ikke så snart var begravelsen til ende, før der igen kom bud til Gyldenstierne om at komme til København. Han ville nødig; men undskyldninger gjaldt ikke, da vigtige regeringssager krævede hans nærvær. Christian 4.'s selvstændige overtagelse af regeringen forestod. Håndfæstningen skulle forud drøftes af rigsrådet og meget andet ordnes. Sommeren og efteråret 1596 tilbragte Gyldenstierne derfor i Danmark. Skiftet i rigsstyrelsen var ikke gunstigt for ham. Ganske vist fik han [[1597]] nyt lensbrev på Akershus; men sine andre len måtte han afstå, og, hvad det værste var, gamle regnskabssager vedrørende lenene (også hvad der stod til rest i hans brors regnskaber) og andre gældsposter kom op og blev meget ubehagelige for ham. Her viste sig formentlig følgerne af, at han havde haft mere at gabe over, end han kunne overkomme. Dertil kom, at statholderposten i Norge næsten havde tabt sin betydning, efter at Christian 4. selv havde overtaget regeringen. Det var derfor efter eget ønske, at Gyldenstierne i [[1601]] fratrådte denne post, samtidig med at han ombyttede Akershus med [[Christianopel]] og [[Sølvitsborg Len]] i nærheden af hans hovedgård Lyngbygård.
 
I april [[1602]] var Gyldenstierne en af den danske konges befuldmægtigede på et grænsemøde i anledning af verserende stridigheder med Sverige. Ikke længe efter blev det overdraget ham at lede det tog, der forestod til Rusland, hvor Christian 4.'s yngste bror, [[Hans af Danmark (1583-1602)|prins Hans]], skulle giftes med zar [[Boris Godunov]]s datter og have store besiddelser i medgift, mens der også skulle føres diplomatiske forhandlinger angående grænsestridighederne mellem Norge og Rusland. Det må betragtes som en stor opofrelse, at Gyldenstierne, som allerede var til års og noget svagelig, overtog dette vanskelige hverv; thi rejser til det mere end halvt barbariske land var den gang forbundet med store farer og besværligheder. Når Gyldenstierne føjede sig efter kongens ønske, selvom han var bekendt med vanskelighederne, så var det måske ikke mindst, fordi der i hans personlige forhold ikke var meget, der holdt ham tilbage. Hans hustru og næsten alle hans søskende var døde, og hans eneste søn, [[Knud Axelsen Gyldenstierne]], forlod samtidig hjemmet for som ung ægtemand at tage bolig på den gamle fædrenegård Tim. Måske også de pekuniære vanskeligheder, som Gyldenstierne i de sidste år havde haft at kæmpe med, har bidraget til, at han med mindre opofrelse forlod fædrelandet. I alle fald gik han 2. august [[1602]] om bord på en eskadre, der skulle føre Hertug Hans med hans talrige følge til Rusland. Gyldenstierne har beskrevet rejsen i en dagbog, der giver bemærkelsesværdige oplysninger om Zarrigets daværende tilstand og om de store besværligheder, det danske selskab havde at overvinde. Da prinsen døde ikke længe efter ankomsten til [[Moskva]], blev der intet af ægteskabet; og de diplomatiske forhandlinger, som var tilbage, frembød så store vanskeligheder, at toget først i juni [[1603]] kunne begive sig hjem.
Personbillede_savnes Politik Historie Ledelse Ledere