The Kingdom of the North is an independent kingdom in Westeros. Following the War of Conquest, the North became one of the constituent regions of the Seven Kingdoms. It has since declared its independence in defiance of the Iron Throne. It was founded during the time of the First Men by Bran the Builder, the first King in the North. At its time of greatest expansion, the Kingdom of the North included all the lands north of the Neck and south of the Gift. Bear Island became part of the Kingdom of the North after King Rodrik Stark won it from the ironborn and the rule of House Hoare in, according to legend, a wrestling match.
The Kingdom of the North was the only kingdom of the First Men that successfully resisted the Andal Invasion and clung to its ways and religion. Southron kingdoms fell and some dynasties were replaced by Andal ones and others were simply absorbed despite family names remaining the same - as was the case of the ancient House Gardener.
Eventually, it was absorbed into the unified monarchy of House Targaryen after King Torrhen Stark bent the knee to Aegon the Conqueror to spare his people from the fate suffered by the armies of the Kingdom of the Rock and Kingdom of the Reach in the Field of Fire.
The Kingdom of the North, however, rises again as one of the consequences of the Execution of Eddard Stark. Robb Stark, Eddard's eldest son and heir, is declared King in the North by his own vassals, as well as the Riverlords sworn to his maternal grandfather, Hoster Tully, the Lord Paramount of the Trident. Thus, the new Kingdom of the North includes all lands historically ruled by House Stark, and the lands surrounding the Trident, ruled by House Tully since the time of Aegon.
During the breakout of the War of the Five Kings, the Kingdom of the North held full control over the lands of the the North and the the Riverlands. After destroying the Lannister army in the Riverlands, King Robb launched a limited invasion of the Westerlands, in order to draw Tywin Lannister out of Harrenhal and finish off his remaining army.
This revived Kingdom of the North would only last two years until the deaths of King Robb and his entire army at the Red Wedding. However, House Bolton, who ruled the North in the aftermath on behalf of the Iron Throne, was narrowly overthrown by House Stark in the Battle of the Bastards due to Sansa Stark summoning the aid of House Arryn, which is nominally headed by her maternal cousin Robin Arryn.
Jon Snow, believed to be Lord Eddard's last living son (but in reality his nephew) after the death of his alleged younger half-brother Rickon Stark, was proclaimed the new King in the North by the Northern lords, despite his bastard status, as well as the Free Folk and the Lords of the Vale. It is unknown, but perhaps likely, that various houses of the Riverlands, such as House Mallister and House Blackwood, will have declared for Jon Snow and the new Kingdom of the North, as they were loyal bannermen to House Tully. Furthermore, these houses are said to be in open rebellion against House Frey, even though the current head of House Tully, Lord Edmure Tully, remains their prisoner. With the deaths of Walder Frey and his two sons, Lothar Frey and Black Walder, at the hands of Arya Stark at the Twins, these houses may be more inclined to once again declare their independence and rejoin the North, especially now that they are joined by the Vale of Arryn, whose lawful ruler Robin Arryn as well as King Jon's surviving alleged half-siblings - Sansa, Arya, and Bran - share blood with House Tully through their mothers, Lysa and Catelyn.
Yet Bran Stark, Lord Eddard's last living trueborn son, has learned through his gift of the greensight, that King Jon is actually his cousin through his aunt, Lyanna Stark. Jon's true father was the Prince of Dragonstone, Rhaegar Targaryen, whose alleged kidnapping of Lyanna along with the subsequent Execution of Rickard and Brandon Stark, his maternal grandfather and uncle, were both the catalyst for Houses Stark, Arryn, and Tully uniting with House Baratheon to overthrow the Targaryen dynasty in Robert's Rebellion. It is unknown if Rhaegar and Lyanna were secretly wed before his conception and whether Jon would then be considered trueborn since Rhaegar was already married to Elia Martell of Dorne. The Targaryens were known for practicing polygamy when they first arrived in Westeros but they gave up the practice to appease the heirarchy of the Faith of the Seven, the dominant religion in the Seven Kingdoms. Polygamy is also proscribed by adherents to the Old Gods of the Forest, some of whom reside in the Vale and the Riverlands as well as the North. This could mean that Jon might still be a bastard in the eyes of most Westerosi, even if his parents were married before his conception, although his status as Lord Eddard's bastard did not stop the lords of the North and the Vale from declaring him king.
Between the threat of the Night King and his army White Walkers and wights and the impending arrival of Daenerys Targaryen and her dragons, what course of action, if any, this new Kingdom of the North will take to stay independent remains to be seen.