In this contribution we demonstrate how a Multicut-based segmentation pipeline can be scaled up to datasets of hundreds of Gigabytes in size. Such datasets are prevalent in connectomics, where neuron segmentation needs to be performed across very large electron microscopy image volumes. We show the advantages of a hierarchical block-wise scheme over local stitching strategies and evaluate the performance of different Multicut solvers for the segmentation of the blocks in the hierarchy. We validate the accuracy of our algorithm on a small fully annotated dataset (5×5×5 μm) and demonstrate no significant loss in segmentation quality compared to solving the Multicut problem globally. We evaluate the scalability of the algorithm on a 95×60×60 μm image volume and show that solving the Multicut problem is no longer the bottleneck of the segmentation pipeline.