Olsztynek signifie Petit Olsztyn en polonais. Déjà au XVe siècle, les sources font déjà mention de Parvum Olstin, un nom ayant une signification semblable au nom actuel. En fait la ville doit son nom à son fondateur, Günter von Hohenstein, le commandeur d'Ostróda, ville voisine située à une trentaine de kilomètres. Holenstein étant le nom allemand d'Olsztyn.
En 1359, le grand maître, Winrich von Kniprode, accorde les droits à la ville. Celle-ci est fondée sur un plan semblable à beaucoup d'autres villes des chevaliers teutoniques. Le point focal est la vaste place du marché, à partir de laquelle partent deux rues perpendiculaires. La ville forme un quadrilatère de 245 x 170 mètres de côté. Elle est entourée de murs d'une hauteur d'environ 10 mètres. À la fin du Moyen Âge, Olsztynek compte environ 450 habitants.
Le , les chevaliers teutoniques subissent une cuisante défaite au cours de la bataille de Grunwald qui se déroule à une quinzaine de kilomètres d'Olsztynek. La ville est prise et incendiée. Elle est rapidement reconstruite, mais les chevaliers qui ont besoin de financer leur contribution aux dommages de guerre, taxent lourdement ses habitants. En 1440, la ville devient membre de la ligue de Prusse, qui s'oppose à l'autorité de l'État teutonique, mais rentre dans le rang lorsque la Pologne lui déclare la guerre en 1454.
