Hypoxia plays a major role in the etiology and pathogenesis of most of the leading causes of morbidity and mortality, whether cardiovascular diseases, cancer, respiratory diseases or stroke. Despite active research on hypoxia-signaling pathways, the understanding of regulatory mechanisms, especially in specific tissues, still remain elusive. With the accessibility of thousands of potentially diverse genomic datasets, computational methods are utilized to generate new hypotheses. Here we utilized Boolean implication relationship, a powerful method to probe symmetrically and asymmetrically related genes, to identify novel hypoxia related genes. We used a well-known hypoxia-responsive gene, VEGFA, with very large human expression datasets (n = 25,955) to identify novel hypoxia-responsive candidate gene/s. Further, we utilized in-vitro analysis using human endothelial cells exposed to 1% O2 environment for 2, 8, 24 and 48 hours to validate top candidate genes. Out of the top candidate genes (n = 19), 84% genes were previously reported as hypoxia related, validating our results. However, we identified FAM114A1 as a novel candidate gene significantly upregulated in the endothelial cells at 8, 24 and 48 hours of 1% O2 environment. Additional evidence, particularly the localization of intronic miRNA and numerous HREs further support and strengthen our finding. Current results on FAM114A1 provide an example demonstrating the utility of powerful computational methods, like Boolean implications, in playing a major role in hypothesis building and discovery.