The first story of Hamlet, originally called Amleth, was told as part of Saxo Grammaticus' Historia, Danica, which was printed in Paris during the 12th Century. This story was then included in Francois de Belleforest's collection of French stories entitled Histoires Tragiques (1576).
It is likely that the version of the story that most directly influenced Shakespeare was a play most probably written Thomas Kyd and acted out in 1594 by two acting companies: the Lord Admiral's Men and the Lord Chamberlain's Men (the latter of which Shakespeare was a member).
Although Shakespeare incorporated many aspects of the earlier stories into his play (such as the basic plot, a love interest for the protagonist, feigned insanity, and a play-within-a-play), he also incorporated classical elements (such as the name Claudius, inspired by Nero's stepfather) and contemporary details as well (such as murdering someone by pouring poison into his ear, which was how the Duke of Urbino was rumored to have died).
Shakespeare also added the Ghost. In the Amleth legend the Claudius character, Feng, openly kills Amleth's father. To avoid being slain himself on the chance Feng would see Amleth as a threat, Amleth feigned being dull-witted. When Amleth goes to England, he befriends the king and marries his daughter. In the end Amleth burns the palace to the ground.