Akcja gry Wieczna Zima: Paleoamerykanie rozgrywa się w Ameryce Północnej około 10 000 lat p.n.e. Gracze poprowadzą swoje plemiona przez kilka pokoleń, przekształcając je ze skromnej grupy łowiecko-zbierackiej w rozwiniętą społeczność plemienną. W czasie rozgrywki plemiona mogą odkrywać nowe ziemie i się na nich osiedlać, rozwijać kulturę, doskonalić techniki polowania na wielką zwierzynę i budować niezwykle trwałe megality.
Wieczna Zima to gra strategiczna łącząca w innowacyjny sposób dwie znane mechaniki: worker placement oraz deck building. W każdej rundzie gracze wysyłają członków swoich plemion na pola na planszy oraz opłacają wybrane przez siebie akcje poprzez zagrywanie kart i wydawanie zasobów. Niezagrane karty mogą zostać wykorzystane na ostatnią fazę rundy, kiedy po ich jednoczesnym odkryciu gracze rozpatrują różnorodne efekty i ustalają nową kolejność tur. Po czterech pełnych emocji rundach wygrywa ten z graczy, którego plemię zdobyło najwięcej punktów zwycięstwa.