In contemporary sources he is alternatively referred to as Sten Gustavsson or Herr Sten (Lord Sten); the practice of using noble family names as part of a personal name was not yet in use in Sweden at the time. He was born around 1440, the son of Gustav Anundsson of the Sture family and Birgitta Stensdotter Bielke, half-sister of the future Charles VIII. The Sture family was one of the high-ranking noble families of the time, though only distantly related to the royal house; his closest royal ancestor was King Sverker II of Sweden (both through family of Vinga and through family of Aspenäs). Sture's father, Gustav Anundsson, was Castellan of Kalmar Castle and a Privy Councillor, but died when the son was four. Birgitta Stensdotter remarried Gustav Karlsson of the Gumsehuvud family, and the son was most likely raised in their home, first at Kalmar Castle and later at Ekholmen Castle.
The 15th century in Sweden was largely defined by the political struggles and civil wars between the unionists of the Kalmar Union, seeking to unite Sweden with Denmark and Norway under the rule of the Danish monarchs, with Danish support, and the separatists seeking to re-establish Sweden as an independent kingdom under a rival Swedish monarch. Due to his close family ties to the Swedish King Charles, the young Sten Sture became part of the Swedish separatist political movement from an early age, and visited Charles during his exile in Danzig. He is mentioned as a knight in 1462 and as a privy councillor in 1466, and took up residence on the family estate at Räfsnäs north of Mariefred. Sture fought with Bishop and Regent Kettil Karlsson Vasa during the uprising against the Danish King Christian I in 1464, taking part in the decisive victory at Haraker. He served as a military commander under King Charles VIII, defeating Erik Karlsson Vasa's uprising at Uppbo in 1470 and later in the same year successfully beating back Christian I's forces at Öresten.
He married Ingeborg Tott, niece by marriage of Magdalen of Sweden, in 1467; she was a renaissance personality interested in theology and science and seems to have had some importance in the intellectual development during his reign. The marriage was childless.