Recent studies suggest that context-specific eQTLs underlie genetic risk factors for complex diseases. However, methods for identifying them are still nascent, limiting their comprehensive characterization and downstream interpretation of disease-associated variants. Here, we introduce FastGxC, a method to efficiently and powerfully map context-specific eQTLs by leveraging the correlation structure of multi-context studies. We first show via simulations that FastGxC is orders of magnitude more powerful and computationally efficient than previous approaches, making previously year-long computations possible in minutes. We next apply FastGxC to bulk multi-tissue and single-cell RNA-seq data sets to produce the most comprehensive tissue- and cell-type-specific eQTL maps to date. We then validate these maps by establishing that context-specific eQTLs are enriched in corresponding functional genomic annotations. Finally, we examine the relationship between context-specific eQTLs and human disease and show that FastGxC context-specific eQTLs provide a three-fold increase in precision to identify relevant tissues and cell types for GWAS variants than standard eQTLs. In summary, FastGxC enables the construction of context-specific eQTL maps that can be used to understand the context-specific gene regulatory mechanisms underlying complex human diseases. For the related source code, see: Github For the preprint, see: biorxiv