This paper first reduces the problem of detecting structural breaks in a random walk to that of finding the best subset of explanatory variables in a regression model and then tailors various subset selection criteria to this specific problem. Of particular interest are those new criteria, which are obtained by means of simulation using the efficient algorithm of Bai and Perron (J Appl Econom 18:1–22, 2003). Unlike conventional variable selection methods, which penalize new variables entering a model either in the same way (e.g., AIC and BIC) or milder (e.g., MRIC and FPEsub) than already included variables, they do not follow any monotonic penalizing scheme. In general, their non-monotonicity is more pronounced in the case of fat tails. The characteristics of the different criteria are illustrated using bootstrap samples from the Nile data set.