I found two articles that had two different findings on the origin on penis.
This ABC News article proposed a 100 million years old evidence of the oldest penis from a fossil of an ostracod, an ancestral crustacean. And surprisingly, this fossil record revealed that they actually had two penises.
This is another article from National Geographic stating that they found the oldest penis fossil record of a 400 million years old spider.
What is surprising is that the National Geographic article was written in year 2003, whereas the ABC News one was written last year. I guess the ABC reporters do not really check upon literature...
I didn't include any graphic photos on this blog, but here's an example of an ostracod male genital.
The top one is the female, and the bottom one represents a male ostracod. The region labeled as Hp is the penis in its relaxed mode.
Next post, I will elaborate on evolution of human penis (without any graphic photos I promise) and in other vertebrates, as well as how they play an important role in sexual selection.
Robin J. Smith, Takahiro Kamiya, David J. Horne. 2006. Living males of the 'ancient asexual' Darwinulidae (Ostracoda: Crustacea). Proceedings of the Royal Society B: Biological Sciences 273:1569-1578.