Nanostructured palladium foams offer exciting potential for applications in diverse fields such as catalyst, fuel cell, and particularly hydrogen storage technologies. We have fabricated palladium nanowire foams using a cross-linking and freeze-drying technique. These foams have a tunable density down to 0.1% of the bulk, and a surface area to volume ratio of up to 1,540,000:1. They exhibit highly attractive characteristics for hydrogen storage, in terms of loading capacity, rate of absorption and heat of absorption. The hydrogen absorption/desorption process is hysteretic in nature, accompanied by substantial lattice expansion/contraction as the foam converts between Pd and PdHx.