High-spin states in 58Ni have been investigated by means of the fusion-evaporation reaction 28Si(32S, 2p)58Ni at 130 MeV beam energy. Discrete-energy levels are observed in 58Ni at record-breaking 42 MeV excitation energy and angular momenta in excess of 30h. The states form regular rotational bands with unprecedented high rotational frequencies. A comparison with configuration dependent cranked Nilsson-Strutinsky calculations reveals an exceptional two-band crossing scenario, the interaction strength of which is strongly shape dependent.