I assume you're referring specifically to parthenogenesis. As all other forms of asexual reproduction are pretty much some form of "cloning" or another, with (unless there's a serious flaw in the process) identical DNA to their parent. Cloning's easy. Everything except a virus uses some method of cloning cells. Even some parthenogenesis is still cloning (uses a "fake" sperm cell that will have no influence over the offspring's DNA- it's pretty well identical to mommy). And THAT is weird enough unto itself- since you'd already need to have evolved to the point where you lost the "hermaphrodite" ability to NEED this variant, meaning something lost and re-invented cloning. That doesn't seem too right, either, but hey, if it happened, it would certainly spread to offspring.
The problem, even with parthenogenisis, is thus: first you have one cell. Then it becomes two cells. Then it becomes four "half cells", aka "sex cell" aka "gametes". Then these cells recombine into a new, slightly different, genetic code. That's a lot of things that have to happen where any single failure at any step means the destruction of the new would-be life form and the cessation of that biological process. Because, until it works, it's a mutation that serves no purpose- and takes up considerable organic resources. The recombination process alone is something that only bacterium can perform under anything less than "perfect" scenarios.
Promoting random uncontrolled mutations in a living creature happens sometimes. The common name for it is cancer. So these new parthenogenically born organisms would have to exist with the intent to be a new separate entity. A new form of non-cloning reproduction. But since cloning reproduction would already exist (clearly, if cloning didn't occur, we wouldn't be having this conversation).
Now once we have parthenogenic life- making the rest of the journey isn't so surprising... self fertilization externally leads to spawning, then that leads to "seahorse" carrying the young methods, then that leads to ever increasingly advanced wombs, and there you have it. By getting rid of the clone method you just sped up evolution by tens of thousands of times over regardless. But we're still facing the "deliberate recombination of cellular material" jump. The part from "can't have sex" to "can and will" have sex.