Ultrahigh-velocity shock waves (similar to 10 000 km/s or 0.03c) are generated by focusing a 350-TW laser pulse into low-density helium gas. The collisionless ultrahigh-Mach-number electrostatic shock propagates from the plasma into the surrounding gas, ionizing gas as it becomes collisional. The shock undergoes a corrugation instability due to propagation of the ionizing shock within the gas (the Dyakov-Kontorovich instability). This system may be relevant to the study of very high-Mach-number ionizing shocks in astrophysical situations.