At first, there were many tribes in New York. Hiawatha, the Great Peacemaker, united 5 of the various tribes to create the Iroquois Confederacy. They became the local power, though the Algonquins and Hurons did make good adversaries. All the tribes seemed to be at war with each other all time, with many dying every day. This in-fighting would make them weak to outside expansion had not a certain tribe came along.
They were the Yua (NOT a real tribe, don't look it up), and used to be located in present day Virginia. They told them about a giant empire to the south, called the Utul, who conquered vast amount of lands. They, not wanting to be assimilated, decided to leave. They wound up right in the middle of the h***hole that is New York. When they first arrived, the tribes stopped fighting each other, curious about the new tribe. They told the story of the Utulans, and how their creation story wound them up here (More on that later). A few days later, the first signs of Utul settlers arrived, and alarmed the tribes. When they started to outright encroach their lands, they met up in a central point, present-day Albany, and discussed what to do. After a while, they realized that in order to keep their style of life, they must band together, and such they did.
Many people that followed their leaders and head back home, but many others decided to stay. After a while, it became a "city", and was decided that it should be the capital.
The name "New York" came from the Yuans. In their story, Man came from a forest paradise (Think Adam and Eve) called "Yok". However, a series of events destroyed the forest, and they wound up in Virginia, but their gods said a paradise north will be set up once barbarians in the south came. It said it would be another heavily forested area with a Giant River (The Hudson) in the center. The Utuls were the "Barbarians" in the story, and, when they told them their story, they wanted to honor it by naming their new confederacy New Yok. However, with their famous New York accent, they pronounced and spelt it "York", but the case still stands.