We present an algorithm to generate unique identifiers to be used for patient identification in the Electronic Health Record (EHR) system for India. A robust EHR system is essential for ubiquitous provision of technology-enabled health-care services. Conventional EHR systems use identifiers such as Social Security Numbers to identify patients. However, in developing nations, adoption of such systems are in its infancy, leading towards the need of an independent identifier generation mechanism to enable patients without conventional IDs to register and avail health-care services. In this paper, we present an approach to generate Unique Health IDentifiers (UHID) for patients to register with EHR systems in the Indian scenario. The approach uses a combination of patient attributes to generate the identifier, and is non-obvious to a naive user. It is capable of generating upto 46; 656 unique identifiers for similar attributes, and offers the added advantage of efficient duplicate detection by using Soundex codes. The effectiveness of the proposed approach has been benchmarked on an actual patient dataset of 1; 992; 102 records, drawn from C-DAC's Hospital Management Information System (HMIS).