Ainu language is traditionally considered as a language isolate. Two main categories of attempts linked Ainu with (1) Altaic or Eurasiatic languages, and (2) Austronesian or Austroasiatic languages. However, these hypotheses have not been widely accepted. The present study argues that Ainu is genealogically connected with the Na-Dene languages in North America. Evidence is presented in three aspects: (1) the existence of many possible cognate etymologies that distributed in body parts, animal-related nouns, artificial objects, and other basic word categories; (2) homologous semantic networks of cognate words and word stems that indicate deep linguistic and cultural intertwines; and (3) regular sound correspondences that are tentatively summarized between Ainu and Na-Dene languages. The position of Ainu in the Dene-Yeniseian and the Dene-Caucasian hypotheses is also discussed. The Ainu-Dene connection, if true, will add an important link between New World and Old World languages, and will shed light on the early migrations of peoples in Beringia and Eurasia.