Avarrocka, later known as Varrock, was built in year 700, 4th Age. Varrock is the oldest surviving human settlement outside the Kharidian Desert in Gielinor today. It was founded when a tribe found a baby abandoned, and took it as a good omen. That baby was Arrav, a famous hero.
Somewhere between 700th and 800th year of 4th age, Zemouregal, a powerful Zamorakian Mahjarrat Necromancer, invaded Avarrocka with an army of zombies to claim the Shield of Arrav, a powerful shield made by now nearly extinct master smith race, imcando dwarfs. His Army was slain by non other than great hero Arrav and the grandson of one of the city's elders with the help of the shield, at the cost of Arrav's life. Zemouregal retreated with undead version of Arrav.
Between years 750-850, the people of Avarrocka became very powerful, and conquered their neighboring tribes, eventually forming the first human nation, Misthalin. Misthalin, in the mid-Fourth Age, however, was little more than a rough conglomeration of tribes, all of whom paid homage to Avarrocka. Nothing that modern scholars would call a nation existed until the end of the Fourth Age.
Between 900 and 1000 years, the government of Avarrocka changed to a monarchy during this period, but the precise date is unknown.
In year 1100-1200, many dark creatures from Morytania attacked Misthalin, especially Avarrocka. Seven priestly warriors defeated them and blessed the River Salve, making it impassable to creatures of Zamorak.
It is not exactly known when was Avarrocka renamed to Varrock. The name "Varrock" is mentioned in Diary of Herbi Flax who supposedly lived in late 4th and early 5th age, suggesting heavily that the change was in mid-late 4th age.