Nathan Birnbaum was born in Vienna into an Eastern European Jewish family with roots in Austrian Galicia and Hungary. His father, Menachem Mendel Birnbaum, a merchant, hailed from Ropshitz, Galicia, and his mother, Miriam Birnbaum (née Seelenfreund), who was born in northern Hungary (in a region sometimes called the Carpathian Rus), of a family with illustrious rabbinic lineage, had moved as a child to Tarnow, Galicia, where the two met and married. Menachem Mendel Birnbaum died when Nathan was eleven. He attended a public high school and gradually drifted away from religious observance but strongly believed in the idea of Jews as a nation.