In biometric identification systems, the biometric database is typically stored in a trusted server, which is also responsible for performing the identification process. However, a standalone server may not be able to provide enough storage and processing power for large databases. Nowadays, cloud computing and storage solutions have provided users and enterprises with various capabilities to store and process their data in third-party data centers. However, maintenance of the confidentiality and integrity of sensitive data requires trustworthy solutions for storage and processing of data with proven zero information leakage. In this paper, we present CloudID, a privacy-preserving cloud-based and cross-enterprise biometric identification solution. It links the confidential information of the users to their biometrics and stores it in an encrypted fashion. Making use of a searchable encryption technique, biometric identification is performed in encrypted domain to make sure that the cloud provider or potential attackers do not gain access to any sensitive data or even the contents of the individual queries. In order to create encrypted search queries, we propose a k-d tree structure in the core of the searchable encryption. This helps not only in handling the biometrics variations in encrypted domain, but also in improving the overall performance of the system. Our proposed approach is the first cloud-based biometric identification system with a proven zero data disclosure possibility. It allows different enterprises to perform biometric identification on a single database without revealing any sensitive information. Our experimental results show that CloudID performs the identification of clients with high accuracy and minimal overhead and proven zero data disclosure.