The first written account we have of the story of Hamlet is found in Gesta Danorum (History of the Danes)by Saxo Grammaticus, a twelfth-century Danish writer. This history is based on earlier sources, including poems, inscriptions, and oral history, and mixes some believable elements with many others that modern historians have determined to be less reliable. It was first printed in Latin in 1514. The key elements of Shakespeare's play are found in the third and fourth books in the story of Amleth, whose uncle murdered his father and married his mother. Amleth pretends to be an imbecile and devises a series of stratagems culminating in the murder of his evil uncle.
The story of Hamlet from Gesta Danorum was retold in French by Francois de Belleforest in 1570. There was also an earlier English play on the same topic by Thomas Kyd which is no longer extant that may have been Shakespeare's main source.
Shakespeare's source for Hamlet is generally accept to have been Thomas Kyd's translation of an old Norse legend that first appeared in the French language in Paris in the 1500s, later appearing in English in 1608. No extant copies exist of Kyd's translation of the Norse tale, but it is called Ur-Hamlet ("ur" means "original). Very little is known of Kyd's work except that it was a tragedy that was performed in London and a character named Hamlet saw a ghost that cried "Hamlet, revenge!"
The old Norse legend was written by Saxo Grammaticus and told the story of the rulers of Denmark. It was called Gesta Danorum, which translates as History of the Danes. The story about the Hamlet prototype is in Books 3 and 4. In Saxo's legend, the King is Rorik. He marries Garuth and they have a son called Amleth. Rorik's brother kills him so he can marry Garuth and become King. Amleth fears for his life and pretends to be mad. He plans revenge, which succeeds, and he becomes the rightful King.