The neutron-rich isotopes Cr58-63 were produced for the first time at the ISOLDE facility and their masses were measured with the ISOLTRAP spectrometer. The new values are up to 300 times more precise than those in the literature and indicate significantly different nuclear structure from the new mass-surface trend. A gradual onset of deformation is found in this proton and neutron midshell region, which is a gateway to the second island of inversion around N=40. In addition to comparisons with density-functional theory and large-scale shell-model calculations, we present predictions from the valence-space formulation of the ab initio in-medium similarity renormalization group, the first such results for open-shell chromium isotopes.