In 1346, the forest was cleared at a location on the Alle River for a new settlement in Prussian Warmia (former German Ermland). The following year, Teutonic Knights began the construction of an Ordensburg castle as a stronghold against the Old Prussians. The German name "Allenstein" refers to a stronghold on the Alle River – which became known in Polish transliteration as Olsztyn. Allenstein received municipal rights in October 1353, and the castle was completed in 1397. The town was captured by the Kingdom of Poland during the Polish-Lithuanian-Teutonic War in 1410, and again in 1414 during the Hunger War, but it was returned to the monastic state of the Teutonic Knights after hostilities ended.
Allenstein joined the Prussian Confederation in 1440 and rebelled against the Teutonic Knights in 1454 upon the outbreak of the Thirteen Years' War. Although the Teutonic Knights recaptured the town the following year, it was retaken by Polish troops in 1463. The Second Peace of Thorn in 1466 designated Allenstein and the Prince-Bishopric of Warmia as part of Royal Prussia under the sovereignty of the Polish Crown.
From 1516 to 1521, Nicolaus Copernicus lived at the castle as administrator of both Olsztyn and Melzak (now Pieniężno). Copernicus was in charge of the Polish defense of Olsztyn during the Polish-Teutonic War of 1519–21.
Olsztyn was sacked by Swedish troops in both 1655 and 1708 during the Polish-Swedish wars, and the town's population was nearly wiped out in 1710 by epidemics of bubonic plague and cholera.
The town became part of the Kingdom of Prussia in 1772 after the First Partition of Poland. Poles became subject to extensive Germanisation policies. A Prussian census recorded a population of 1,770 people, predominantly farmers, and Allenstein was administered within the newly created Province of East Prussia. It was visited by Napoleon Bonaparte in 1807 after his victories over the Prussian Army at Jena and Auerstedt. By 1825, the town was inhabited by 1341 Germans and 1266 Poles. The first German-language newspaper, the Allensteiner Zeitung, began publishing in 1841. The town hospital was founded in 1867.
In 1871, with the unification of Germany under Prussian hegemony, Allenstein became part of the German Empire. Two years later, the city was connected by railway to Toruń. Its first Polish language newspaper, the Gazeta Olsztyńska, was founded in 1886. Allenstein's infrastructure developed rapidly: gas was installed in 1890, telephones in 1892, public water supply in 1898, and electricity in 1907. In 1905, the city became the capital of Regierungsbezirk Allenstein, a government administrative region in East Prussia. From 1818 to 1910, the city was administered within the East Prussia Allenstein District, after which it became an independent city.
Shortly after the outbreak of World War I in 1914, Russian troops captured Allenstein, but it was recovered by the Imperial German Army in the Battle of Tannenberg. The battle took place closer to Allenstein than to Tannenberg (now Stębark), but the Germans, recalling their defeat in the 1410 Battle of Grunwald (German: Battle of Tannenberg), named it "Tannenberg II" for nationalistic reasons.
After the defeat of Germany in World War I, the East Prussian plebiscite was held in 1920 to determine whether the populace of the region, including Allenstein, wished to remain in German East Prussia or become part of Poland. In order to advertise the plebiscite, special postage stamps were produced by overprinting German stamps and sold on 3 April of that year. One kind of overprint read PLÉBISCITE / OLSZTYN / ALLENSTEIN, while the other read TRAITÉ / DE / VERSAILLES / ART. 94 et 95 inside an oval whose border gave the full name of the plebiscite commission. Each overprint was applied to 14 denominations ranging from 5 Pfennigs to 3 Marks. The plebiscite was held on 11 July, and produced 362,209 votes (97.8%) for Germany and 7,980 votes (2.2%) for Poland.
The football club SV Hindenburg Allenstein played in Allenstein from 1921 to 1945. After the January 1933 Nazi seizure of power in Germany, Jews in Allenstein were increasingly persecuted. Also anti-Polish sentiment became more visible. The Gazeta Olsztyńska was abolished by the German authorities, the newspaper's headquarters was demolished and the editor-in-chief Seweryn Pieniężny was arrested and executed in the Hohenbruch German concentration camp. In 1935, the German Wehrmacht made the city the seat of the Allenstein Militärische Bereich. It was then home of the 11th and 217th infantry divisions and 11th Artillery Regiment.
On 12 October 1939, after the German invasion of Poland that began World War II, the Wehrmacht established an Area Headquarters for a military district that controlled the environs of Allenstein, including Lötzen (now Giżycko), and Ciechanów in occupied Poland. Beginning in 1939, members of the Polish-speaking minority, especially members of the Union of Poles in Germany, were persecuted or deported back to Poland.
On 22 January 1945, near the end of the war, Allenstein was plundered and burned by the conquering Soviet Red Army, and much of its German population fled. On 2 August 1945, the city became part of Poland under border changes promulgated at the Potsdam Conference, and officially became the Polish "Olsztyn". In October 1945, the remnants of the German population were forcibly expelled.
A tire factory was founded in Olsztyn in 1967. Its subsequent names included OZOS, Stomil and Michelin.
In 1989 the former Gazeta Olsztyńska headquarters was rebuilt and re-opened as a museum.
Olsztyn became the capital of the Warmian-Masurian Voivodeship in 1999. It was previously in the Olsztyn Voivodeship.