It is of interest to detect structural breaks in high dimensional time series data, together with the parameters of the statistical model employed to capture the relationships amongst the variables/features of interest. An additional challenge emerges in the presence of very large data sets, namely on how to accomplish these two objectives in a computational efficient manner. We outline a novel procedure which leverages a block segmentation scheme (BSS) that reduces the number of model parameters to be estimated through a regularized least squares criterion. Specifically, BSS examines appropriately defined blocks of the available data, which when combined with a fused lasso based estimation criterion, leads to significant computational gains without compromising on the statistical accuracy in identifying the number and location of the structural breaks. The procedure together with additional screening steps consistently estimates the number and location of break points. It is further applicable to various statistical models, including regression, graphical models and vector-autoregressive models. Extensive numerical work on synthetic data supports the theoretical findings.