Many crystals, such as those of metals, can transform from one symmetry into another having lower free energy via a diffusionless transformation. Here we create binary colloidal crystals consisting of polymer microspheres, pulled together by DNA bridges, that induce specific, reversible attractions between two species of microspheres. Depending on the relative strength of the different interactions, the suspensions spontaneously form either compositionally ordered crystals with CsCl and CuAu-I symmetries, or disordered, solid solution crystals when slowly cooled. Our observations indicate that the CuAu-I crystals form from CsCl parent crystals by a diffusionless transformation, analogous to the Martensitic transformation of iron. Detailed simulations confirm that CuAu-I is not kinetically accessible by direct nucleation from the fluid, but does have a lower free energy than CsCl. The ease with which such structural transformations occur suggests new ways of creating unique metamaterials having structures that may be otherwise kinetically inaccessible.