In this paper we develop a method to estimate a route choice model where we allow for random link costs. Such route choice models allow for a natural correlation structure across paths, and they are also quite useful to simulate routes once they have been estimated. Although useful from an applied point of view, they have been difficult to estimate consistently. Instead, many different approaches have been suggested, for instance logit based models. Such models often rely on choice set generation, and since there does not exist any known correction method, at least for models with a flexible correlation structure across paths, it is difficult to know how good they are. The purpose of this paper is to show that simple models that are most likely misspecified may be very useful as an auxilliary model when estimating the true model in an indirect inference approach. The idea is that it is easy to simulate the true model, and by constructing simulated data sets we may use the auxiliary model to find the true parameters in a structured way. The simulation evidence shows that it is quite feasible to estimate a route choice model with random link costs on realistic sized networks and data sets. Our main conclusion is that indirect inference is an exciting option in the tool box for route choice estimation.