Things do not "speciate" into sexes; both sexes are the same species.
Mammals evolved from reptiles (via some now extinct intermediaries), reptiles already reproduced sexually, reptiles evolved from tetrapods that also reproduced sexually, they, in turn, reproduced from sexually reproducing fish. In fact, as far as I know, Pikaia, the earliest representative of the Chordates (the group that contains all creatures with backbones) appears to have been sexually reproducing. So, in fact, we don't know when sexual reproduction evolved, just that it happened prior to about 550 million years ago in the group that led to mammals.
Current thoughts on the matter is that it evolved roughly 1200 million years ago, in single celled organisms.