Archeological evidence suggests that the first settlement was established near Gihon Spring around 4500–3500 BC. The first known mention of the city was in c.2000BC in the Middle Kingdom Egyptian Execration Texts in which the city was recorded as Rusalimum. The root S-L-M in the name is thought to refer to either "peace" (compare with modern Salam or Shalom in modern Arabic and Hebrew) or Shalim, the god of dusk in the Canaanite religion.
The Book of Genesis 14:18, mentions a city called Salem, which most Jewish commentators believe refers to Jerusalem, ruled by King Melchizedek, whose name means "my king is zedek", where Zedek is believed to refer either to the Canaanite deity Sydyk or the word righteous. According to one Jewish tradition reported by the midrash, Jerusalem was founded by Abraham's forefathers Shem and Eber.