Complex hydrides are attracting increasing attention as promising solid hydrogen storage materials, yet theoretically exploring their chemical space is a challenging task due to their often intricate structures. In this work, we present an improved evolutionary crystal structure prediction method tailored to systems with rigid building blocks, enabling a reduction in search space dimensionality without losing relevant solutions and significantly speeding up the search. The developed method was validated by successfully reproducing the known structures of borohydrides and alanates of lithium, sodium, and potassium, while also revising their vibrational and energetic properties.Furthermore, this approach, together with in-depth phonon analysis, led to the prediction of a new metastable P 3cm phase of Ca(BH4)2 , only 1.5 meV/atom above the known ground state. This phase exhibits a layered geometry unusual for complex hydrides, combining covalent, ionic, and van der Waals bonding, with the potential for both chemical and physical hydrogen storage via intercalation.