The Faroe Islands (Færeyjar) and Iceland (Island) were settled by the Norse in the 9th Century CE. There is some evidence of prior settlement by hermetic monks known as Papar, but this is inconclusive.
Colonisation of North America began with Eiríkr Rauði's (Erik the Red) exile from Iceland in 982. He spent his three year exile exploring up the coast of Greenland (Grœnland), and gathered a group of colonists once his exile expired. In total 25 ships made the journey, and only 14 arrived in Greenland. At its height, the Norse settlement would reach 5000 people. Unfortunately, Erik the Red would be the victim of his own success - a group of immigrants in 1002 brought along an epidemic that would cost him his life.
When Greenland was first settled, one of the fourteen ships had been blown off course, sighting land further west. Erik's son Leifr (Leif) took this information and ventured further west in 1001. He first landed in Helluland (Baffin Island), before venturing south to Markland (Present-day Labrador). Finally, Leif and his crew continued south and landed at Vinland, staying for the winter at Leifsbúðir. There they met natives that they would call "skrælingi" to distinguish them from the Inuit who resided further north. Relations were initially OK, until Leif's brother Þorvaldr (Thorvald) got into a fight with them and was killed by an arrow in 1003.
Leifsbúðir had been established as a ship repair and navigation outpost, but the conflict with the skrælings in 1003 led to its temporary abandonment. Then in 1009, Þorfinnr Karlsefni (Thorfinn the Valiant) led a voyage back to Leifsbúðir with around 250 people. After the winter, about 100 of them stayed at Leifsbúðir to inhabit and defend the area, and Thorfinn ventured further south with the remaining ~150. They eventually landed at what they would call Straumfjörð, in present day Mira Bay off of Cape Breton Island, Nova Scotia. There again relations with the skrælings were alright, with some trade taking place. The relationship was still quite tense though, and a fight broke out after one of Thorfinn's bulls escaped and spooked the natives. The natives began to charge the Norse, and while most of the Norse men ran away into the woods, Freydís Eiríksdóttir (daughter of Erik the Red) did not - in fact, she could not, as she was eight months pregnant. Instead, she pulled up a sword, exposed her breast, and let out a warcry, scaring off many of the natives instead.
After this incident, the natives and Norse mostly kept their distance, but still occasionally traded with each other.
By the 1040s, the population of Straumfjorð had grown to about 300 people thanks to further immigration. While the climate was better than that of Leifsbúðir (which was better than the climate of Greenland), its winters were still very cold. Recent winters trended colder still, and this created some pressure to settle further south.
In 1041, Freydís's son Mikjáll Freydisson* (the one she was pregnant with in the 1010 CE skirmish with the natives) gathered a small crew to explore further down the coast. After finding a spot in present day Lobster Bay, Nova Scotia (the southwestern tip), he gathered 120 men, women, and children to set sail in the early spring of 1042. The voyage soon ran into trouble though, encountering a strong out-of-season nor'easter. While everyone survived the storm, it pushed them too far southwest and out to the sea.
*Unlike many Norse names, Mikjáll traditionally has a matrynomic last name rather than a patrynomic one. His father is much less well known to history, so his mother's name is used instead. It's unknown if his contemporaries used patrynomic, matrynomic, or both names.The ships used were not designed to make a journey through the sea, but were just meant to go along the coast. Given the situation, Mikjáll decided to turn north and find the closest land, and then take stock of the situation. Soon, they saw it - the archipelago they would name Skrælingyjar.
The small fleet made landfall at what would later be called Smarvik, a small bay on the southern side of Storreyn. The settlers gathered together to figure out their next steps: should they return to Straumfjorð, or should they take a look and consider settling this new land. After some discussion, three small exploration parties were formed to gather intel. One party would go north up the coast, one south, and Mikjáll would lead a party of five northwest over the mountain (Mt. Þorr) to get a better vantage point. Since it was already the afternoon, they all setup camp and would start exploring at dawn.
Unbeknownst to the settlers, a small Abenaki hunting party was on the mountain, and noticed the strange ships landing on the coast. They reported back to their village, and sent a party out the next morning to meet the strangers. They eventually met in an opening in the woods to the west of Mt. Þorr. At this point, the Norse already had some experience meeting native "skrælings". After some careful, slow attempts at communication, the natives seemed alright with the Norse settling nearby. Of course, this may have had something to do with numbers - it looked like there was just about as many Norse people as there were Abenaki on the island.
The expedition parties returned later that day, and everyone made the trek over the mountain to the Siguan River. There they found a fertile valley downstream from the Abenaki, and got to work chopping down trees, building houses, and planting seeds to establish Skrælingborg. The settlers traded some of their tools for corn, an unfamiliar crop that the natives insisted would grow well. This combination of crops from the Old and New Worlds would lead to a more stable system of agriculture than was practiced in other Norse colonies, and it is theorized that this adaptation is part of why Skrælige survived through this day.
The rest of the 1040s saw the settlement develop further, without expanding much. As the natives had said, the corn grew really well. Combined with the regular harvest, winter did not present the same problems that European colonists would run into over five centuries later. Work began on replacing the small wooden church with a larger stone one, which still stands to this day. The thatched earthfast houses were reinforced with wood, and more structures were built to better accommodate the settlers.
Unlike with previous Norse colonies, there were no hostilities... for the first couple of years. This changed in the summer of 1045, when some fishermen ventured upstream between the two Abenaki villages. Up until this point, the natives and Norse stayed fairly separate, but now it looked like the settlers were encroaching on Abenaki land. An argument devolved into a violent fight and resulted in several deaths, including all the fishermen and some natives.
The Abenaki tribe gathered their warriors and hid in the woods surrounding Skrælingborg, ready for an ambush. A small Abenaki diplomatic party entered the city to demand an audience with Mikjáll Freydisson. He and some other heads of household met with the Abenaki who then revealed some of their warriors. The village was surrounded, and caught completely off guard. The Abenaki were merciful, however, and were just there to demand that the settlers stay downstream. Given the choice between staying downstream and the likely destruction of the entire village, it was an obvious choice.
In the aftermath, the various assembled heads of households decided that they had to form some sort of authority to better organize the settlement. This assembly, or þing, is the ancient predecessor to Skrælige's current parliament. There were three things to discuss:
Whether to leave for some other land away from the natives. (This was discussed, but then voted against unanimously.)
If any counter-attack should be launched.
How to better prepare for an attack in the future.
The settlers had clearly been caught out by the Abenaki - if they had chosen to attack, the settlement could have been completely wiped out. Although many wanted to avenge the deaths of the fishermen, they were not prepared to raid the main settlement. Effort went into building fortifications around the town, and patrols were setup to keep guard against any future ambush.
After fortifying the settlement, life in Skrælingborg was fairly stable. This made it attractive for more immigration from further east, including a large group of around 60 people in 1053. A second similarly-sized group migrated in 1057, along with another common guest on medieval ships - disease. The exact disease is unknown, but it was deadly. Around 10-25% of the Skræligens died. Due to some trade contact, 20-50% of the natives perished as well.
The Norse settlement suffered greatly, but the native society was devastated. The widespread death was on a scale they had never witnessed before, leading to many doubting their religion and way of life. While the Norse people hadn't been doing much missionary work (themselves fairly recent converts to Christianity), they were welcoming of natives integrating into their society and religion. The Skræligen Abenaki still survived as their own culture as well, but they would never recover to their earlier peak. Skrælige was firmly in the hands of the settlers of Skrælingborg.
Through the next decades, Skrælige recovered and prospered. Mikjáll Freydisson passed away some time around 1080, but the þing continued to function as Skrælige's government without many issues. Outside of Skrælige, Norse settlement continued:
Eynavik was established down the coast from Leifsbúðir in 1051, but was abandoned later that year after fights with local natives.
Humarvik was founded in 1064 where Mikjáll had originally intended to land.
The island of Anticostynar was occupied between 1062 and 1068, but a series of poor harvests forced the settlers to leave.
Temporary settlements were built in Helluland and Markland, but were generally not inhabited through the winters.
The settlements in Greenland continued to grow and prosper.
The end of the 11th century marked the expansion of Skræligen settlement into two additional towns: Miðrtunga & Smarvik.
Miðrtunga was the new name of the middle Abenaki village that had integrated with the Skræligens after the epidemic. It was given the name when it formally integrated into Skrælige in 1062, sending its own heads of household to the Þing.
Smarvik was the original landing site of the Norse in 1042 before they migrated north to the Siguan River. Depending on the winds, it was sometimes easier for the ocean-going ships to land here, so a few people decided to live there permanently and to help facilitate these landings.
There's a few divergences from our timeline that I want to draw attention to:
First of all, the permanent settlement at Leifsbuðir in 1009 is a divergence. In our timeline it was a ship repair outpost, but this timeline will expand the scale of the settlement.
There's some debate about where Straumfjörð really was, so this timeline decides on Mira Bay in Nova Scotia. The possible locations are listed on Wikipedia, but instead of picking the most plausible I went for the one that fit in the best with the location of Skrælige.
Straumfjörð's settlement is also a point of divergence - as far as I could tell, it was abandoned at some point after the fighting, but I'm not sure how much afterward.
Skrælige's founding figure, Mikjáll Freydisson, is the son of Freydís. I couldn't find any information on her children, so I made this one up.
The name Mikjáll has its earliest observed usage in 1350 in OTL - I've brought that forward by a few centuries. Since the Norse had Christianized around the turn of the millennium, this shouldn't be too much of a stretch.
I didn't see much information about Freydís's husband, let alone a name, so I made a matrynomic last name instead.
The epidemic had a bad impact on the natives, but its impact was not as bad as OTL's Columbian Exchange. This is due to the lack of smallpox, which wasn't endemic to Iceland or other far western Scandinavian lands. Other European diseases were still deadly, but not to the same extent as smallpox.