The discovery of upstream regulatory genes of a gene of interest still remains challenging. Here we applied a scalable computational method to unbiasedly predict candidate regulatory genes of critical transcription factors by searching the whole genome. We illustrated our approach with a case study on the master regulator FOXP3 of human primary regulatory T cells (Tregs). While target genes of FOXP3 have been identified, its upstream regulatory machinery still remains elusive. Our methodology selected five top-ranked candidates that were tested via proof-of-concept experiments. Following knockdown, three out of five candidates showed significant effects on the mRNA expression of FOXP3 across multiple donors. This provides insights into the regulatory mechanisms modulating FOXP3 transcriptional expression in Tregs. Overall, at the genome level this represents a high level of accuracy in predicting upstream regulatory genes of key genes of interest.