Początki hokeja sięgają końca XV wieku. Dyscyplina została prawdopodobnie zapoczątkowana w Anglii lub Francji. W kulturze po raz pierwszy hokej można zaobserwować w malarstwie niderlandzkim – np. na obrazie Pietera Bruegla Myśliwi na śniegu z 1565. Na jego dalszym planie widać ludzi korzystających z zakrzywionych kijów. Jeszcze wcześniej pojawił się na namalowanym w roku 1494 ołtarzu św. Kryspiana i Kryspiniana.
Użycie słowa hokej w odniesieniu do gier rozgrywanych na lodzie datuje się dopiero na 1785 rok (w 1527 do gier rozgrywanych na zamarzniętych stawach), mimo to etymologia tego terminu nie jest pewna. Możliwe, że pochodzi od francuskiego słowa hoquet, co znaczy pasterski kij lub zgięty kij.
Udokumentowane początki nowoczesnej gry miały miejsce w Ameryce Północnej. Za kolebkę hokeja jest uznawana Kanada. Gra została wymyślona w 1855 roku w Ontario przez stacjonujących tam angielskich żołnierzy, którzy nudzili się podczas długich zim uniemożliwiających uprawianie innych sportów zespołowych. 3 marca 1875 roku w kanadyjskim Montrealu odbył się pierwszy mecz hokeja na lodzie w hali Victoria Skating Rink. Spotkanie rozegrano pomiędzy dwiema drużynami składającymi się z dziewięciu zawodników. Kapitanem jednej z drużyn był James Creighton – organizator meczu. Zawodnicy grali drewnianym krążkiem, używając przy tym łyżew i kijów. Mecz trwał 60 minut.