In order for vertebrates to evolve from the sea to the land, some drastic evolutionary changes were needed.
Their ancient sea-dwelling ancestors had no need for external sex organs whereas their land relatives did.
Now a new study offers insights into the genetic changes that allowed land-dwelling animals to develop sex organs.
The Nature research suggests the key to the origin of genitalia lies in the limbs, at least in snakes and lizards.
For their genitals - called hemipenes - to develop, a signalling centre instructs the relevant genes to switch on.
Initially the researchers wanted to understand why snakes do not develop limbs but then soon discovered that the earliest stages of genital development closely resembled limb formation.
They found that when a given nudge, embryonic limb cells of lizards and snakes could then be turned into genitals. In mice, tail bud cells could be manipulated in a similar way.
The team did this by moving the position of "a signalling source" called the cloaca - a transient embryonic structure which gives off signalling molecules informing genes to switch on or off.
"It demonstrates that there is a flexibility with what kind of cells can get recruited during development to form genitalia," explained lead author of the research, Dr Patrick Tschopp from the Harvard Medical School in Cambridge, US.
"What we were able to show is that if you ectopically transplant this cloaca into either limb or tail bud cells, these cells respond in a way that reflect their development being redirected to a genital fate," he added.
"In other words, by misplacing a molecular signal you can misguide these cells in their developmental trajectory," Dr Tschopp told BBC News.
In order to change these cells' fates, they traced the cell populations that form genital organs during development.
Then they analysed the genetic components of the embryonic cells to identify which genes were turned on and off by extracting and sequencing RNA molecules, the messengers from each gene.
The study also found that in mice, the sex organs had genetic origins in the tail bud. The researchers say that this occurred due to a differing position of the cloaca which changed the cells it could "recruit" to form genitalia.
Dr Tschopp explained that genital evolution was another adaptive measure vital for living on land, in a similar way to how limbs have an evolutionary origin in fish fins.
Commenting on the paper, developmental biologist Dr Liang Ma of Washington University in St Louis, US, said the work was fantastic, and that it was highly important for the fields of both genitalia and limb research.
"This paper dealt with the longstanding unresolved issue of the origin of genitalia. It turns out that the mouse is the odd one out, it was not similar to the snakes or the chicken.
"This paper provides a new twist to a previous hypothesis that genitals and limbs share a deep homology [shared ancestry], it provides formal evidence of how this co-evolution between the two structures can happen in an organism."
In a related study published in journal Scientific Reports, a team looked at the embryonic origins of chicken genitals. They used fluorescent dyes to label small populations of cells in the chicken embryo and follow them to development.
They found that two paired populations of cells are brought together into one structure to form the chicken's sex organs.
Co-author of this paper, Prof Martin Cohn of the Howard Hughes Medical Institute in Maryland, US, said that because the evolution of external genitals occurred more rapidly than any other organ, there was a tremendous amount of diversity of anatomical form. "Because of the rapid evolution, people don't really understand how it's controlled.
"Taken together, I think the papers highlight a very deep evolutionary conservation of the earliest steps in genital development. It appears that the way all amniotes, including reptiles, birds and mammals, build their genitalia is very similar.
"What these molecular and genomic tools allow us to do is compare the degree of relatedness, not only of the structures and the organisms, but of the genetic pathways that build those structures," Prof Cohn added.