In this paper we introduce a new approach to the generation of binary sequences by applying trace functions to elliptic curves over GF(2m). We call these sequences elliptic curve pseudorandom sequences (EC-sequences). We determine the periods, distribution of zeroes and ones, and linear spans for a class of EC-sequences generated from super-singular curves. We exhibit a class of EC-sequences which has half period as a lower bound for their linear spans. EC-sequences can be constructed algebraically and can be generated efficiently in software and hardware by the same methods that are used for implementation of elliptic curve cryptosystems.