Neményi was born to a wealthy Hungarian-Jewish family on June 5, 1895, in Fiume (Rijeka) in the Kingdom of Hungary. His grandfather was Siegmund Neumann who magyarized his family to Neményi in 1871 and part of the family became Christians. Pauls father Dezső Neményi was one of the directors at Rijeka Refinery (now INA d.d.). His mother was Julianna Goldberger de Buda (or Buday= von Buda), born 1868 in Budapest, as at least, the fifth consecutive generation Goldberger to do so. Neményi attended elementary and high school in Fiume (Rijeka). He graduated from high school in Budapest. Neményi's uncle was Dr. Ambrus Neményi, born in Pécel, c. 20 km east of Budapest. Paul Neményi's aunt was Berta Koppély (whose parents were Adolf Koppély (1809–1883) and Rózsa von Hatvany-Deutsch). His family's art collection included works by Klimt, Kandinsky and Matisse.