Gyldenstierne deltog i Kristian II:s krigståg mot Sverige 1520 men tog sedan Fredrik I:s parti. Han besatte Akershus 1527 och försvarade som länsherre framgångsrikt fästningen vid Kristians restaurationsförsök 1531. År 1532 fick han i stället Malmöhus som län. Vid grevefejdens utbrott 1534 fängslades Gyldenstierne kortvarigt och stödde sedan en tid den