Eckstein was born on 14 June 1868 in Coburg to Johann Nikolaus Eckstein and Anna Barbara Eckstein, née Götz. Her father was a porter and assistant telegraphist at the
Werra-Eisenbahn-Gesellschaft, a railway company. Eckstein had a younger brother named Ernst and an older sister named Antonie (Toni), who was born with a disability. Financial reasons limited her formal education to attending a girl's school from 1874 to 1882. However, Eckstein's teacher Ottilie Frese supported her in learning English and French, which made her want to become a teacher herself. She was confirmed in the main church of Coburg in 1882.
At the age of 16, in September 1884, Eckstein left Germany to visit relatives in New York. The reasons for this are unclear. Her parents might have wanted to prevent her from forming a relationship with an aristocrat who was out of her range, or it was to support her teaching career. For the first few years she worked as a maid or teacher at various places and then took on a job as a private teacher for the daughter (Mamie) of a Jewish merchant (Godfrey Mannheimer) who had immigrated from Germany. While working in this household from December 1887 to October 1893 she joined the Mannheimer family on three trips to Germany.