2 of 4 added 133 characters in body

The Zohar writes that the Patriarch Yitzchok had the soul of a female.

Additionally, the Arizal explained that Michal wore tefillin because she had a male soul (h/t Gershon).

So it seems that souls do have genders, both male and female.