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 remained the same - as was the case of the ancient House Gardener.
The Kingdom of the North was absorbed into the unified monarchy of House Targaryen after King Torrhen Stark swore allegiance to Aegon the Conqueror to spare his people from the fate suffered by the armies of the Kingdoms of the Rock and the Reach in the Field of Fire.
The Kingdom of the North, however, rises again as one of the consequences of the execution of Lord Eddard Stark. Eddard's heir, Robb Stark is declared King in the North by his own vassals, as well as the Riverlords sworn to House Tully. 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, The Kingdom of the North launched a limited invasion of the Westerlands, in order to draw Tywin Lannister out of Harrenhal and finish off his remaining army.
Robb Stark's revived Kingdom of the North would only last two years until the death of King Robb and his entire army at the Red Wedding.
However, House Bolton, who ruled the North in the aftermath of the Red Wedding on behalf of the Iron Throne, was overthrown by House Stark at the Battle of the Bastards. After the battle, Jon Snow, believed to be King Robb's bastard half-brother (Actually his paternal first cousin), was proclaimed the King in the North by the northern lords, 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 had been loyal bannermen to House Tully which was a former part of the Kingdom. Furthermore these houses are said to be in open rebellion by Walder Frey, alongside Riverrun, the seat of House Tully, against House Frey's control over the Riverlands. With Walder Frey's death, along with his two sons Lothar Frey and Black Walder, at the hands of Arya Stark, the Riverlands may be more inclined to re-declare their independence and rejoin the North.