Nal Hutta and Nar Shaddaa
The Hutts had owned a small province on Evocar as soon as the Hutt Empire was formed, two centries before they ousted the Evocii, in 25,200 BBY. In 25,100 BBY, the defeated Xim the Despot died in the dungeons of Kossak the Hutt's palace on Evocar (Tionese historians claimed that Xim was treacherously killed at the Third Battle of Vontor).
Old Republic
After the Hutts had escaped the destruction of their home world Varl in 25,000 BBY, they migrated across space and came to Evocar. Having decided that Evocar was a suitable home, they traded their technology with the Evocii in exchange for pieces of land on Evocar. The Hutts continued doing this until the Evocii realized that their home world had almost been bought out from under them. Hutt palaces, amusement parks and other constructions were built all over Evocar, and the Evocii could do nothing about it. The Hutts destroyed the planet's lush mountainous rainforest's, terraforming the planet into what they considered paradise: stinking (to Humans) bogs, scum-covered puddles, and patches of sickly marsh grass full of insects and spiders.
They appealed to the Galactic Republic, though the Republic sadly ruled in favor of the Hutts in 25,000 BBY. The Evocii were eventually evicted from Evocar by the Hutts, and relocated to the planet's fifth moon, which would later be known as Nar Shaddaa, The Smuggler's Moon. The Hutts then destroyed the remaining Evocii agriculture and the original terrain and then terraformed (the destroyed) remaining patches of land as well.
When the Evocii were evicted to Nar Shaddaa they were enslaved to build the cities of the moon enforced by the Hutts beginning in 25,000 BBY. Although Nar Shaddaa was only starting to be built it quickly began to prosper along with Nal Hutta itself under the new Galactic Republic. Five centuries later the entire moon was urbanized and the Evocii were freed of their labor by the Hutts since their work was complete. Since that year Nar Shaddaa rivaled Coruscant as a center of instastelar trade and Nal Hutta prospered even more by its side.
However,in 24,000 BBY when the trade routes shifted, Nal Hutta and its moon became havens for smugglers, pirates, and other criminals. During the same year, without the treatment of the Republic the Evocii were out casted into the planet's moon's under city and began to mutate into savages due to various technologies practiced on the moon. However the Hutts did side with the Honorable Union of Desevro & Tion during the same year when the the trade lanes shifted. Thus Nal Hutta presumably became a enemy Fortress World of the Republic during the Tionese War.
In 23,900 BBY The Republic turned the Hutt allies against the Honorable Union of Desevro & Tion in order to defeat them. The Union was indeed defeated and the Tionese war came to a close. Thus Nal Hutta along with its moon lost even its alternate government and both became completely independent and truly began to fall into ruin and disrepair.
As of the First Jedi Purge Nal Hutta was enslaving refugees after buying them from the Exchange from the Refugee Sector on Nar Shaddaa in 3,951 BBY.
Galactic Empire
During the Galactic Civil War, the Galactic Empire established nominal control over Nal Hutta, but for the most part the Hutt ruling families were left to control day to day affairs, with the Empire stepping in only when searching for Rebel sympathizers or other criminals.
