In short, the Nameless King is the Firstborn of Gwyn. What we have long known about the Firstborn is that he was a god of war that was stripped of his status. This is from the Ring of the Suns Firstborn:
Ring of the Sun's first born, who inherited the light of Gwyn, the first lord. Greatly boosts miracles. The Sun's first born was once a god of war, until he was stripped of his stature as punishment for his foolishness. No wonder his very name has slipped from the annals of history.
The Nameless kings soul refers to the Nameless King as a dragon slaying god of war until he sacrificed everything to ally with the dragons, so that seems to match the firstborns story perfectly. The Soul of the Nameless King:
Soul of the Nameless King. One of the twisted souls, steeped in strength. Use to acquire many souls, or transpose to extract its true strength. The Nameless King was once a dragon-slaying god of war, before he sacrificed everything to ally himself with the ancient dragons.
Further confirmation of the Nameless Kings identity comes from his armor, which is said to greatly resemble Gwyns. From the Golden Crown;
Crown of a nameless king who was ally to the ancient dragons. This golden crown, buried amidst long strands of bristling ash, is said to closely resemble that of the First Lord.
So we finally learn the Nameless Kings foolishness; he made allies with his fathers great enemy. Its not known exactly why he did this, but the in-game tale that is told by the Lightning Storm miracle that describes his bond with a storm drake may tell of this:
Miracle of the Nameless King, ally to the ancient dragons. Calls forth furious bolts of lightning. Once a slayer of dragons, the former king and wargod tamed a Stormdrake, on which he led a lifetime of battle. This miracle is likely a tale of their bond.
More evidence of the Nameless Kings bond with the stormdrake comes from the Storm Curved Sword, which also implies that claiming the souls of your allies is tradition amongst the gods. This might explain why the Giant Blacksmith could transpose souls in Dark Souls 1, and the behavior of Ornstein and Smough in their boss battle.
Curved sword imbued with the strength of the Stormdrake. The Nameless King, ally of the ancient dragons, fought beside the Stormdrake in countless battles. When the great beast fell, the king claimed his soul, as was the custom in the age of gods.
The Nameless King was also Ornsteins lord more so than Gwyn was, as Ornstein is said to have been his first knight. From the Leo Ring:
Ring associated with Dragon Slayer Ornstein, one of the Four Knights of Gwyn, the First Lord. Strengthens thrust weapon counter attacks.Ornstein was the first knight of the sun's eldest born, and his cross spear is said to have pierced scales made of stone.
This is further expanded upon in the description of the Dragonslaver Swordspear, as it was the basis of the cross spear that Ornstein would become famous for later on.
A dragon hunting weapon from the age of the gods. The earliest form of the cross spear, serving as both a sword and a spear. Its owner was the Nameless King, a deific hunter of dragons. The swordspear is imbued with lightning, of which he was the heir.
The last thing to be said about the Nameless King is that Ornstein left Anor Londo to look for him. This is said in the Dragonslayer Helm:
Golden Lion Helm associated with Dragonslayer Ornstein, from the age of gods, and imbued with the strength of lightning. In the dragonless age, this knight, who long guarded the ruined cathedral, left the land in search of the nameless king.
As this was done while Smough was still alive and guarding Anor Londo, this confirms that the Ornstein fought in Dark Souls 1 was naught but an illusion. Smoughs Great Hammer:
Twisted great Hammer associated with Smough, the last knight to remain at his post, guarding the ruined cathedral.Restore HP while attacking, a carryover from Smough's past as an executioner.