The Gauss-Markov theorem provides a golden standard for constructing the best linear unbiased estimation for linear models. The main purpose of this article is to extend the Gauss-Markov theorem to include nonparametric mixed-effects models. The extended Gauss-Markov estimation (or prediction) is shown to be equivalent to a regularization method and its minimaxity is addressed. The resulting Gauss-Markov estimation serves as an oracle to guide the exploration for effective nonlinear estimators adaptively. Various examples are discussed. Particularly, the wavelet nonparametric regression example and its connection with a Sobolev regularization is presented.