The halide ions of organic-inorganic hybrid perovskites can strongly influence the interaction between the central organic moiety and the inorganic metal halide octahedral units and thus their lattice vibrations. Here, we report the halide-ion-dependent vibrational coherences in formamidinium lead halide (FAPbX, X = Br, I) perovskite nanocrystals (PNCs) via the combination of femtosecond pump-probe spectroscopy and density functional theory calculations. We find that the FAPbX PNCs generate halide-dependent coherent vibronic wave packets upon above-bandgap non-resonant excitation. More importantly, we observe several higher harmonics of the fundamental modes for FAPbI PNCs as compared to FAPbBr PNCs. This is likely due to the weaker interaction between the central FA moiety and the inorganic cage for FAPbI PNCs, and thus the PbI unit can vibrate more freely. This weakening reveals the intrinsic anharmonicity in the Pb-I framework, and thus facilitating the energy transfer into overtone and combination bands. These findings not only unveil the superior stability of Br-based PNCs over I-based PNCs but are also important for a better understanding of their electronic and polaronic properties.