Extracytoplasmic Ni(II)-binding proteins (NiBPs) are molecular shuttles involved in cellular nickel uptake. Here, we determined the crystal structure of apo CcNikZ-II at 2.38 Å, which revealed a Ni(II)-binding site comprised of the double His (HH-)prong (His511, His512) and a short variable (v-)loop nearby (Thr59-Thr64, TEDKYT). Mutagenesis of the site identified Glu60 and His511 as critical for high affinity Ni(II)-binding. Phylogenetic analysis showed 15 protein clusters with two groups containing the HH-prong. Metal-binding assays with 11 purified NiBPs containing this feature yielded higher Ni(II)-binding affinities. Replacement of the wild type v-loop with those from other NiBPs improved the affinity by up to an order of magnitude. This work provides molecular insights into the determinants for Ni(II) affinity and paves way for NiBP engineering.