For an infinite word \alpha=\alpha_0\alpha_1\alpha_2\dots, over a finite alphabet A, we define the maximal pattern complexity by p_\alpha^*(k)=\sup_\tau\sharp\{\alpha_{n+\tau(0)} \alpha_{n+\tau(1)}\dots\alpha_{n+\tau(k-1)}; n=0,1,2,\dots\} where the ‘sup’ is taken over all subsequences 0=\tau(0)<\tau(1)<\dots<\tau(k-1) of integers of length k. We prove that \alpha is eventually periodic if and only if p_\alpha^*(k)\le 2k-1 for some k. Infinite words \alpha, with p_\alpha^*(k)=2k for any k, are called pattern Sturmian words and are studied.