Nazwa Pierwotna nazwa zamku i miasta Olsztynek brzmiała Hohenstein. Pochodzi ona od nazwiska rodowego jego założyciela, komtura ostródzkiego Günthera von Hohensteina. Nazwisko Hohenstein, znane też jako Hohnstein (współcześnie Honstein), pochodzi od nazwy zamku Hohnstein w Neustadt/Harz w regionie Harzu w Turyngii. Nazwa ta oznacza wysoki zamek, wysoka twierdza. Arystokratyczny ród Hohensteinów pochodził z Ilfeld i od XII wieku władał hrabstwem Hohnstein (dziś powiat Nordhausen). Jego członkowie wstępowali do zakonu krzyżackiego już od początku XIII wieku.
Obecna nazwa jest powstałym już w średniowieczu spolszczeniem nazwy niemieckiej. Polscy przybysze do Prus spolszczali zarówno nazwę Hohenstein, jak i Allenstein na Olsztyn, na wzór znanego im Olsztyna koło Częstochowy, odróżniając Olsztyn Mały i Olsztyn Duży. Jan Długosz w XV w. przy opisie kampanii grunwaldzkiej zapisał nazwę zbliżoną znaczeniem do obecnej – Parvum Olstyn, dosł. „Mały Olsztyn”. W późniejszych wiekach utrwaliła się forma Olsztynek, która miała odróżniać go od większego Olsztyna na Warmii.
Mieszkaniec Olsztynka to olsztynczanin, a mieszkanka – olsztynczanka. Przymiotnik od nazwy tego miasta to olsztynecki.