Sourcing medical experience in finding effective patient-treatment strategies is challenged by strict privacy requirements these days. Specifically, the cross-institutional discovery of “similar” patients based on certain attributes, e.g., to align treatment strategies or collect clinical expertise on rare diseases, is currently either impossible, impractical, or it exposes sensitive data. Addressing this research gap, we propose PatDiscover, which is a fully homomorphic encryption-based design that supports multiple attribute types of medical importance, such as Enum, Range, and Distance. This way, institutions may compose and submit complex queries to several other institutions to discover relevant patients elsewhere. We evaluate PatDiscover extensively using real-world patient data from nuclear medicine and demonstrate its adequate performance, scalability, precision, and security for real-world use. In conclusion, our work enables the privacy-preserving discoverability of patients for various applications in healthcare (research) and beyond.