Pierwsze wzmianki o Warmii, jeszcze sprzed podboju krzyżackiego, pochodzą ze źródeł duńskich. Z około 1210–1231 pochodzi najstarszy zapis w formie Ermelandia zawarty w Liber Census Daniae, zbiorze dokumentów podatkowych króla Danii Waldemara II Zwycięskiego, który w 1210 roku podporządkował czasowo wybrzeża pruskieRafał Simiński Ziemie pruskie w świetle źródeł duńskich do przełomu XIII-XIV wieku, Pruthenia, tom IV, Olsztyn 2009..
Pod nazwą Warmia kraina występuje powszechnie w dokumentach łacińskich – kościelnych, polskich i krzyżackich – od roku 1242.
Pochodzenie nazwy Warmii nie jest pewne, jednak zwykle wywodzi się ją od pruskiego słowa wormyan oznaczającego kolor czerwony i spokrewnionego ze słowem „czerw, robak”. Wiąże się to najprawdopodobniej z pozyskiwaniem na pobrzeżach Zalewu Wiślanego larw czerwca polskiego (Porphyrophora polonica), które były używane jako czerwony barwnik w procesie barwienia tkanin. Nazwa Warmii znaczy więc najprawdopodobniej „czerwona kraina” lub „kraina czerwców”Stanisław Achremczyk Historia Warmii i Mazur. Pradzieje – 1772, Olsztyn 2010, tom I, s.