Flechtheim was born in Nikolaev (then Russian Empire, now Mykolaiv, Ukraine), into a Jewish family, the son of bookseller Herrmann Flechtheim (1880-1960) and his wife Olga, née Farber (1884-1964).
His family being secular, Flechtheim did not receive religious upbringing.