The goal of this article is to display a Q-polynomial structure for the Attenuated Space poset Aq(N,M). The poset Aq(N,M) is briefly described as follows. Start with an (N+M)-dimensional vector space H over a finite field with q elements. Fix an M-dimensional subspace h of H. The vertex set X of Aq(N,M) consists of the subspaces of H that have zero intersection with h. The partial order on X is the inclusion relation. The Q-polynomial structure involves two matrices A,A⁎∈MatX(C) with the following entries. For y,z∈X the matrix A has (y,z)-entry 1 (if y covers z); qdimy (if z covers y); and 0 (if neither of y,z covers the other). The matrix A⁎ is diagonal, with (y,y)-entry q−dimy for all y∈X. By construction, A⁎ has N+1 eigenspaces. By construction, A acts on these eigenspaces in a (block) tridiagonal fashion. We show that A is diagonalizable, with 2N+1 eigenspaces. We show that A⁎ acts on these eigenspaces in a (block) tridiagonal fashion. Using this action, we show that A is Q-polynomial. We show that A,A⁎ satisfy a pair of relations called the tridiagonal relations. We consider the subalgebra T of MatX(C) generated by A,A⁎. We show that A,A⁎ act on each irreducible T-module as a Leonard pair.