The electric dipole polarizabilities of Ni-12-Ni-58 have been measured via a molecular beam deflection experiment. The majority of the clusters display polarizabilities alpha between 4 and 6 Angstrom (3) per atom, below the atomic value of 6.8 Angstrom (3) and above that predicted for ideal conducting spheres. Local extrema in alpha /atom are observed for certain Ni-n. In particular, those clusters that adopt closely packed or quasispherical structures (e.g., Ni-38, Ni-55) display local minima, while Ni-21, Ni-22, Ni-25, and Ni49-54, each an icosahedron or polyicosahedron with "missing" atoms, display anomalously high values. The relationship between the polarizabilities of nickel clusters and their shapes and structures is discussed.