The integers are well-ordered.
If I take the entire set of integers though, there is no least element! Isn't the entire set of integers a valid subset of the integers?
Or (and I suspect this is the case), subset here is really in the very strictest of senses (i.e. $\mathbb{Z} \not\subset \mathbb{Z}$)?
The integers are not well-ordered. Take, for example, the subset of all even integers - there is no least element.
I think you're thinking of the naturals, $\mathbb{N}$, in which case this is true.