Characterization of the austenite phase at high temperatures is important for understanding the microstructural evolution during steel processing. The austenite phase structure can be reconstructed from the room-temperature microstructure employing the crystallographic orientation relationship between the parent and product phases. The actual orientation relationships in steels are often calculated on the basis of well known relations (e.g. Kurdjumov-Sachs), which may differ from the experimentally observed orientation relationships. This work introduces a new approach to improve the current state of the art in prior phase reconstruction. The proposed approach consists of two new algorithms that are sequentially applied on an electron backscatter diffraction (EBSD) measured data set of the product phase microstructure: (i) an automated identification of the optimum orientation relationship using the observed misorientation distribution of the entire EBSD scan and (ii) reconstruction of the parent phase microstructure using a random walk clustering technique. The latter identifies groups of closely related grains according to their angular deviation from the proposed orientation relationship. The results were validated by near in situ experimental observations of phase transformation in an Fe-Ni alloy whereby the experimentally measured parent phase structure could be compared point by point with the reconstructed counterpart.