Delay Tolerant Networks (DTNs) have emerged as communication paradigm for providing end-to-end communication based on store-carry-forward mechanisms without the need for costly infrastructure. However, empirical studies have shown that integrating opportunistically encountered infrastructure—e.g., Internet access via WiFi—into hybrid DTNs can significantly boost routing performance. Nevertheless, extending sophisticated DTN protocols for decentralized routing towards and across the infrastructure is both complex and insufficiently understood. In this paper, we present the overlay-based Hybrid Routing System (HRS) which is—to the best of our knowledge—the first decentralized and collaborative approach for routing in hybrid DTNs that does not rely on central servers. With HRS, a large class of existing DTN protocols can benefit from opportunistic infrastructure encounters, as we show by integrating three prominent representatives of this class into HRS. In an extensive simulation study we show that (1) hybrid routing in a decentralized setting is indeed possible and can significantly boost the performance of sophisticated DTN routing protocols, (2) routing towards the infrastructure can be implemented independently for the message destination in a scalable way, and (3) communication and storage overhead can be kept low since target-oriented message forwarding across the infrastructure can avoid heavy message replication.