In 1220 Prussians invaded territories of Conrad of Masovia, in reaction Conrad called on the pope and the emperor for a Crusade. The results were edicts calling for Crusades against the "marauding, heathen" Prussians. Many of Europe's knights joined in these Crusades, which lasted sixty years. In 1243, the Papal legate William of Modena divided Prussia into four bishoprics, Culmland, Pomesania, Warmia (Ermland), and Sambia (Samland) under the archbishopric of Riga.

In 1237 the Teutonic Knights absorbed the Order of the Sword Knights (established 1202 in Livonia), increasing the occupied regions by the territories of today's Latvia and Estonia. Since the Monastic Prussia and Livonia did not have a common border, it was the aim of the Teutonic Knights' politics in the 14th century to incorporate the Lithuanian province of Samogitia, in order to join the lands ruled by the Order.

The pope installed the Teutonic Knights, a crusading order that reported directly to the Papacy, as rulers of the area. Under their governance, woodlands were cleared and marshlands made arable. Many cities and villages were founded upon those lands, including Marienburg(Malbork).

At the beginning of the 14th century, the neighboring region of Pomerania was plunged into war involving Poland and Brandenburg to the west. Brandenburg's claim to Eastern Pomerania was based on a treaty of August 8, 1305 between Brandenburg's rulers and Wenceslaus III, which promised the Meissen territory to the Bohemian crown in exchange for Eastern Pomerania.

During the course of the war, the city of Gdansk was seized (November 1308) by the Teutonic Knights, called in by king Władysław Łokietek (Ladislaus the Elbow High) of Poland. Based on the subsequent stagnation and reversal in the development of Gdansk, some historians claim that all the inhabitants of the city, both Polish and German, were slaughtered, but this massacre is disputed by other historians. The Teutonic Order continued its invasion of the Polish lands, incorporating them into its domains. In September 1309, Margrave Waldemar of Brandenburg sold his fictitious claim to the territory to the Teutonic Order for 10,000 marks. This was also the start of a series of conflicts between Poland and the Teutonic Order.

Possession of Gdansk by the Teutonic Order was not recognised by the Polish kings Władysław Łokietek (Ladislaus the Elbow High) and Casimir the Great and led to a series of bloody wars and legal claims in the papal court in 1320 and 1333. Finally in 1343 peace was concluded when the Teutonic Knights accepted that they should rule Eastern Pomerania as a fief of the Polish crown. Polish kings retained the right to the title Duke of Pomerania.

In 1410, with the death of the emperor Rupert, war broke out between the Teutonic Knights and a Polish-Lithuanian alliance supported by Ruthenian and tiny Tatar auxiliary forces, in which Poland and Lithuania were the winners following their victory at Battle of Grunwald. The Order assigned Henry XIII, duke of Reuss-Plauen, to defend Pomerania. He moved rapidly to bolster the defence of Marienburg, was elected vice-grand master and saved the Marienburg headquarters. He then became grand master and in 1411 concluded the First Treaty of Thorn with king Ladislaus II of Poland.

In March 1440, the Hanseatic cities of Gdansk, Elblag and Torun and gentry (mainly from Chelmno Land) founded the Prussian Confederation with other Prussian cities to free themselves from the overlordship of the Teutonic Knights. They asked king Casimir IV of Poland to support their revolt and incorporate Prussia into Poland (February 1454), and when he agreed the War of the Cities or Thirteen Years' War started. The resulting Second Treaty of Thorn (October 1466) provided for the Teutonic Order's cession to the Polish crown of its rights over the western half of its territories, which became the province of Polish or Royal Prussia. The eastern half of Prussia remained under the rule of the Order and its successors, until 1660 under Polish overlordship.

During the Reformation endemic religious upheavals and wars occurred, and in 1525, the last Grand Master of the Teutonic Knights, Albert of Brandenburg, a member of a cadet branch of the house of Hohenzollern, resigned his position, adopted the Lutheran faith and assumed the title of "Duke of Prussia." In a deal partially brokered by Martin Luther, Ducal Prussia became the first Protestant state. In 1618 the dukedom of Prussia passed to the senior Hohenzollern branch, the ruling Margraves of Brandenburg.

See also Prussia, Prussia (province)