Introduction: The registration of histological whole slide images is an important prerequisite for modern histological image analysis. A partial reconstruction of the original volume allows e.g. colocalization analysis of tissue parameters or high-detail reconstructions of anatomical structures in 3D. Methods: In this paper, we present an automatic staining-invariant registration method, and as part of that, introduce a novel vessel-based rigid registration algorithm using a custom similarity measure. The method is based on an iterative best-fit matching of prominent vessel structures. Results: We evaluated our method on a sophisticated synthetic dataset as well as on real histological whole slide images. Based on labeled vessel structures we compared the relative differences for corresponding structures. The average positional error was close to 0, the median for the size change factor was 1, and the median overlap was 0.77. Conclusion: The results show that our approach is very robust and creates high quality reconstructions. The key element for the resulting quality is our novel rigid registration algorithm.