We present a study of the structural evolution of palladium cluster anions in a size range from 55 to 147 atoms using a combination of trapped ion electron diffraction and density functional theory computations. We show that Pdn- clusters (n = 55, 65, 75, 85, 95, 105, and 147) change from an icosahedral motif at Pd55- to the bulk fcc motif at Pd147-. This size-dependent structure transition is probed experimentally at a temperature of 95 K and characterized by a continuously increasing fraction of fcc isomers over the considered size range showing a crossover to the fcc motif at n ≈ 90.