In the year 1381, the Danish prince Harald went on a journey with some fishermen, interested in their tales of lands in the west. They landed in OTL Newfoundland (named Prince-Haralds-Land, eventually shortened to Haraldsland), meeting some Indians. Prince Harald claimed the land in the name of the Danish king, returned to Europe together with some Indians, presenting them to the astonished courts of Europe. In the following years, several other ships would go to the New World, return with plants and animals. After the first curiosity had ebbed, people in Europe mostly didn't care about any more, though. A few fishermen made settlement on Prince-Haralds-Land, Cape Cod and Manhattan Island, but that was all for the moment.
1435, Black Death hit the New World, destroying some small European settlements too; other trade places had to be given up, since the Atlantean trade partners had died or didn't want to have contact with the Europeans any more. They now concentrated on a few places: Haraldsland, New Jutland (Nova Scotia), Prince-Harald-Island (Manhattan), Nieuw Zeeland (Atlantic City island), plus the Scottish-Norwegian colony on Martha's Vineyard.
After the separation of their countries, the kings of Denmark and the Netherlands finally agreed in 1438 for a compromise in the New World, which was negotiated by the pope: Denmark kept the northern colonies (Prince-Harald-Island, Haraldsland, New Jutland), which were extended with time over the whole OTL Canadian Maritimes and the Hudson valley. The Netherlands got the Southern colony of Nieuw Zeeland and were allowed to colonize the lands further South.
In 1471, Anders Christensen discovered the mouth of St Lawrence river, but was killed a bit later by Atlanteans, so the expedition decided to return. Another Danish expedition reached Lake Ontario in 1475. Soon, the first Danish colonies along St Lawrence river were founded. Together with the colonies of Prince-Harald-Island and Anderland, they formed a belt around the English colonies. For the northern lands, the name Markland became common.
After some clashes with Danish colonists in Atlantis, the Quadruple Monarchy declared the anti-Danish War (1509-12) against Denmark. The Dutch allied with the former. In the peace of Hamburg, Denmark lost its lands in Canada to the Quadruple Monarchy and Anderland to the Netherlands. Only the city of Haraldsborg (OTL New York, plus Long Island) and Prince-Haralds-Land (as a base for fishermen) stayed in their hands.
When the Triple Monarchy of England-Castille-Portugal broke apart in the Old World 1628, most of the colonies declared their loyalty to Spain (former Castille, right). Only a few islands in the Caribbean and the northern colonies in OTL Canada and New England stayed loyal to king Henry VI. But as soon as 1637, the Dissenter's Revolt broke out in New England. Denmark-Braunschweig, supported by France, used the situation to expand there / take old lands back. Only Markland could defend itself during this decades, ironically, thanks to its strong garrison. Denmark-Braunschweig got Haraldsborg back, plus became protector of the Commonwealth of New England (the dissenters preferred "the papist German king in Europe to the papist English governor in Markland"). The English loyalists emigrated to Markland.
After having accepted the loyalty of Markland, king Humphrey I planned to regain England's old colony in North Atlantis. However, the states of Denmark-Braunschweig and Florence allied against him in the "Atlantean Coalition" and surprisingly defeated the English fleet several times during 1652-56. New England stayed a Danish-German protectorate.
During the anti-French War, Canada saw the battle of Kingsburgh (OTL Montreal) in November 1687. As a result, the French-Atlantean troops had to cease the siege and retreat to French Quebec. 1694, in the peace of Amsterdam, Quebec became English too and was later united with Markland to form Canada.