Archeological finds within the Kathmandu Valley show it to have been inhabited as early as 900 BC. It is noted that the Buddha and his disciples spent some time in the area where present day Patan is located within the Kathmandu Valley in the 6th century BC. Four stupas around the city of Patan erected by Ashoka the Great, a Mauryan King, in the 3rd century BC attest to the ancient history present within the valley. The Kirats are the first documented rulers of the Kathmandu Valley, the remains of their palace are said to be in Patan near Hiranyavarna Mahavihara called "Patukodon". The Licchavi dynasty whose earliest inscriptions date back to 464 AD were the next rulers of the valley and had close ties with the Gupta Dynasty of India. The Malla dynasty ruled Kathmandu from the twelfth century till the seventeenth century when the Shah Dynasty under Prithavi Narayan Shah conqured the valley as he created present day Nepal. Most of ancient Nepalese Architecture present in Kathmandu today is from the Malla era.

According to legend, the area was a lake in the past, but Manjushri, a disciple of the Shakyamuni Buddha, cut open a hill to the south and allowed the water to flow out, making the region habitable. The origin of the present name is unclear, but one of the more likely theories is that it was named after Kastha-Mandap ("temple of wood" in Sanskrit), after a pagoda carved from the single tree on the order of King Lakshmi Narasingha Malla in 1596.