Fornication comes from the word fornix, which means "arch." In Roman times, customers used to identify the brothels by a prominent archway at the entrance. (Coincidentally, we refer to the anterior, posterior, and lateral fornices as components of the uterus, but we also have a fornix in the brain, so interpret that as you will).
HT: My Gross Anatomy Prof
Disclaimer: I take no responsibility for the possibility that this is all urban legend.