We develop a nonlinear martingale theory for time discrete processes $(Y_n)_{n\in \NN_0}$. These processes are defined on any filtered probability space $(\O,\F,\F_n,\P)_{n\in\NN_0}$ and have values in a metric space (N,d) of nonpositive curvature (in the sense of A. D. Alexandrov). The defining martingale property for such processes is \[ \E(Y_{n+1}|\F_n)=Y_n, \qquad \P\mbox{-a.s.,} \] where the conditional expectation on the left-hand side is defined as the minimizer of the functional \[ Z\mapsto\E d^2(Z,Y_{n+1}) \] within the space of $\F_n$-measurable maps $Z\dvtx \O\to N$. We give equivalent characterization of N-valued martingales (using merely the usual linear conditional expectations) and derive fundamental properties of these martingales, for example, a martingale convergence theorem. Finally, we exploit the relation with harmonic maps. It turns out that a map $f\dvtx M\to N$ is harmonic w.r.t. a given Markov kernel p on M if and only if it maps Markov chains $(X_n)_{n\in\NN}$ (with transition kernel p) on M onto martingales $(f(X_n))_{n\in\NN}$ with values in $N$. The nonlinear heat flow $f\dvtx \N_0\times M\to N$ of a given initial map $f(0,\cdot)\dvtx M\to N$ at time n is obtained as the "filtered expectation," \[ f(n,x) := \E_x [ f(X_n) |\!|\!| (\F_k)_{k\ge 0}] \] of the random map $f(X_n)$. Similarly, the unique solution to the Dirichlet problem for a given map $g\dvtx M\to N$ and a subset $D\subset M$ is obtained as \[ f(x) := \E_x [ g(X_{\tau(D)})|\!|\!| (\F_k)_{k\ge 0}]. \] In both cases, a crucial role is played by the notion of filtered expectation $\E_x [\cdot |\!|\!| (\F_k)_{k\ge 0}]$ which will be discussed in detail. Moreover, we prove Jensen's inequality for expectations and filtered expectations and we prove (weak and strong) laws of large numbers for sequences of i.i.d. random variables with values in N. Our theory is an extension of the classical linear martingale theory and of the nonlinear theory of martingales with values in manifolds as developed, for example, in Emery and Kendall. The goal is to extend the previous framework towards processes with values in metric spaces. This will lead to a stochastic approach to the theory of (generalized) harmonic maps with values in such "singular" spaces as developed by Jost and Korevaar and Schoen.