We introduce a discrete-time fractional calculus of variations on the time scale \(h\mathbb{Z}\), \(h > 0\). First and second order necessary optimality conditions are established. Examples illustrating the use of the new Euler-Lagrange and Legendre type conditions are given. They show that solutions to the considered fractional problems become the classical discrete-time solutions when the fractional order of the discrete-derivatives are integer values, and that they converge to the fractional continuous-time solutions when \(h\) tends to zero. Our Legendre type condition is useful to eliminate false candidates identified via the Euler-Lagrange fractional equation.