Nils Gyldenstolpen isä oli Turun akatemian rehtori Mikael Wexionius, aateloituna Gyldenstolpe (1650). Hänen äitinsä oli Susanna Crucimontana (1617–1669), joka oli Algutsbodan kirkkoherran, maisteri Nicolaus Svenonis Crucimontanuksen ja Magdalena Gripin tytär.
Hänen ensimmäinen puolisonsa oli Christina Wärnschöld (1653–1672), toinen Margareta Ehrensteen (1659 Helsingør – 1721 Tukholma). Margareta Ehrensteenin kanssa heille syntyi ainakin neljä poikaa: Edvard Gyldenstolpe (1679–1709), Carl Adolf Gyldenstolpe (1681–1709), Gustaf Gyldenstolpe (kuoli lapsena) ja Ulrik Nils Gyldenstolpe (1689–1768). Hänen kaksi poikaansa kuoli Pultavan taistelussa hieman ennen isänsä kuolemaa.