Paul Kleiman wurde im Jahr 1917 in Wisnowiec Nowy, Polen geboren. Er war der Sohn von Michael und Miriam. Vor dem Zweiten Weltkrieg lebte er in Wisnowiec Nowy, Polen. Während des Krieges war er in die Sowjetischen Streitkräfte. Paul überlebte die Shoah.