We introduce a quantile regression framework for analyzing high-dimensional heterogeneous data. To accommodate heterogeneity, we advocate a more general interpretation of sparsity which assumes that only a small number of covariates influence the conditional distribution of the response variable given all candidate covariates; however, the sets of relevant covariates may differ when we consider different segments of the conditional distribution. In this framework, we investigate the methodology and theory of nonconvex penalized quantile regression. We also propose and study a quantile-adaptive nonlinear variable screening procedure. The theory of these new methods require considerably weaker conditions than those for the least squares based procedures in high dimension. Numerical studies confirm the fine performance of the proposed methods.