Given an elliptic curve C, we study here N_k = #C(F_q^k), the number of points of C over the finite field F_q^k. This sequence of numbers, as k runs over positive integers, has numerous remarkable properties of a combinatorial flavor in addition to the usual number theoretical interpretations. In particular, we prove that N_k = -W_k(q,-N₁), where W_k(q,t) is a (q,t)-analogue of the number of spanning trees of the wheel graph. Additionally we develop a determinantal formula for N_k, where the eigenvalues can be explicitly written in terms of q, N₁, and roots of unity. We also discuss here a new sequence of bivariate polynomials related to the factorization of N_k, which we refer to as elliptic cyclotomic polynomials because of their various properties.