We study the problem of incorporating covariates in a compound decision setup. It is desired to estimate the means of $n$ response variables, which are independent and normally distributed, and each is accompanied by a vector of covariates. We suggest a method that involves non-parametric empirical Bayes techniques and may be viewed as a generalization of the celebrated Fay-Herriot (1979) method. Some optimality properties of our method are proved. We also compare it numerically with Fay-Herriot and other methods, using a `semi-real' data set that involves spatio-temporal covariates, where the goal is to estimate certain proportions in many small areas (Statistical-Areas)