Chołodecki was born in 1852 in Stawki [uk] in the Galician region of the then Austro-Hungarian empire, close to the present day city of L'viv in Ukraine.

Chołodecki was the son of Celestyn, a writer and a nadleśniczy of the forestry department in Galicia, and Emilia from the house of Setti da Forli.

His academic studies began at home, and continued at primary school in Stryj located in present-day Ukraine.

In 1873, a year prior to finishing his law degree, Józef applied to the Directors of the Lwów postal service.

[citation needed] In his first literary endeavors, books and pamphlets printed from the presses of Gazeta Polska, Chołodecki wrote under the pseudonym of Walenty Ćwik, this included his historical book about Bukowina in 1884, an examination of the history of the Polish Navy and Polish artillery in 1885, and a biography of Henryk Schmitt in 1888.

Finally he presented his literary ambitions to the minister of trade, and due to his influence through his position at the postal service in Lwów, he was granted the right to publish books under his name.

Some of his many historical works include: "Revere the memory of your forebears, revere your forefathers graves: With their acts and service, sustain your spirit, sustain your strength..." Polish: "Czcij przodków twych pamięć, czcij ojców mogiły: W ich dziełach, zasługach krzep ducha, krzep siły..."