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 (later named Prince-Haralds-Land, which was eventually shortened to Haraldsland), meeting some Indians. Prince Harald claimed the land in the name of the Danish king. In the following years, several other ships would go to the New World, returning 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.
In 1435, the 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.
1438, the kings of Denmark and the Netherlands finally agreed for a compromise in the New World, 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.
After some clashes with Danish colonists in Atlantis, the Quadruple Monarchy declared war (1509-12) against Denmark. The Dutch allied with them. In the peace of Hamburg, Denmark lost its lands in OTL 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.
Denmark had fought in the anti-French War on France's side. In the Peace of Amsterdam 1694, Prince-Haralds-Land was ceded by Denmark-Braunschweig to England.
With some help from German Atlantis, Canada could win independence in 1822, only Haraldsland stayed British. But quite soon, after the Anti-British War (1832-36) of allied New Rome, Germany, German Atlantis and Canada, in the peace of Roma Nuova, Britain had to cede Haraldsland to Canada, making it a new province.