When he was an old, old man, Rustem really did die (according to the story in the Shahnameh). Rustem died from treachery and betrayal, by his own half-brother Shaghad.
One day Rustem was riding through the forest on his horse Rakhsh, when suddenly they fell into a pit. Shaghad had dug this deep pit on the trail and covered it with branches and mud, so nobody could see it, just to trap Rustem. The ruler of Kabulistan (Afghanistan) helped Shaghad with his evil plan. These two set poisoned spears standing upright in the bottom of this pit.
So, when Rustem and his horse Rakhsh fell into this pit, they fell on the poisoned spears. Raksh lay dying, and Rustem was dying too. Shaghad was standing by the pit laughing at them. Rustem said "Well, you have killed me at last." He asked his half-brother Shaghad for a bow and two arrows, as his last wish before he died. Shaghad brought Rustem the bow and the two arrows, and then started to run away. But Rustem shot his arrow right through the trunk of a tree and killed Shaghad - and then Rustem died.
There's a similarity between this story and the death of Robin Hood that makes us think the two stories may be related. This story, in the Shahnameh, was written about 1000 AD, and the earliest version of Robin Hood's death by treachery may have been written in the 1100s AD, and was certainly being told by the 1400s. But the earliest version that mentions Robin Hood shooting an arrow dates to the 1700s.