A fundamental task in the analysis of time series is to detect structural breaks. A break indicates a significant change in the behaviour of the series. One method to formalise the notion of a break point, is to fit statistical models piecewise to the series. To find break points, the endpoints of the pieces are varied as is their number. A structural break is indicated by a significant change of the model parameters in adjacent pieces. Both, varying the pieces and repeatedly fitting models to them, are usually computationally very expensive. By combining genetic algorithms with a preprocessing of the time series we design a very fast algorithm for structural break detection. It reduces the time for model-fitting from linear to logarithmic in the length of the series. We show how this method can be used to find structural breaks for time series which are piecewise generated by AR(p)-models. Moreover, we introduce a nonparametric model for which the speed-up can also be achieved. Additionally we briefly present simulation results which demonstrate the manifold applications of these methods. A reference implementation is available at http://www2.imm.dtu.dk/~pafi/StructBreak/index.html