The first gender-segregated bathroom facilities in the modern era date from a 1739 ball in Paris, but that’s not quite that simple. In fact, toilet use was segregated earlier than that: this is simply the first noted occurrence of a toilet facility expressly for women. Contemporary restaurants in London, for example, had permanent toilet facilities for male patrons only. Women were expected to carry around a sort of premodern Shewee or portable urinal if they were so bold as to venture out in public, or some such. Presumably there would be someplace private to use it if necessary.
You’ll notice, of course, the expectation that women seen in public society could afford to buy these ceramic or glass Shewees. Sheila Cavanaugh argues that the development of gender-segregated toilets in 18th and 19th century Europe was a function of highlighting and heightening class divisions through gender policing. The polite and genteel would of course not deign to bare themselves in front of the other gender. She notes that the famous Paris restaurant actually enforced the use of bathrooms by gender by specifying (male) “valets” to guard the men’s and (female) “chambermaids” for the women’s toilet area.
And in fact, the creation of women’s toilet facilities in public places was both a recognition of women’s increasing consumer power over the course of the 19th century into the 20th, and an enabler of increased acceptance of women in public. As late as 1900, Canadian store owner Timothy Eaton was insisting that providing public toilets for women specifically was necessary to his business, since peeing on the go would enable them to shop for longer.
That describes what we might call the origins of the modern, Western public bathroom divide. For the Middle Ages, the most interesting evidence for segregated “public” toilet facilities comes from the Islamic world. Muslim legal scholars discussing sea travel give us some insights into normative ideals, although how much that reflects practice is probably an open question.
Scholars express deep concern over the need to keep men and women separate during sea travel, despite the essential impossibility in close quarters. Sources present this as very much a question of preventing the development of sexual attraction–it is not a class issue, as it seems to have become in later Europe.
One strand of legal writing prescribed women not to travel on ships at all (but of course). However, since there were not just women travelers but women ship owners in the medieval Islamic world, others scholars stepped in with provisions. Most typical is the requirement that men and women have different living quarters, period, including male and female slaves. This would include toilet facilities but is not specific. However, scholar al-Mawardi does specify explicitly different bathroom areas “so that [women] are not exposed to view when they need to use them” (trans. Khalilieh).
Medieval European residences might have a cloaca (privy tower) or garderobe in more upscale private dwellings. Certainly men and women in the same household would share their privy if they had one (or presumably use the same bucket if they did not and could not make it to the public latrine in time); there are court cases specifically referring to the privy of a husband and wife pair. A few elite families might have had private latrines for the women’s household, as did Elizabeth de Burgh.
There were also typically public latrines in medieval cities. However the sources refer exclusively to men using them (accidents where men fall through rotted seats and drown in the cesspool below; murder cases where one man chases another into the latrine or lurks outside in wait). On the other hand, bathhouses were mixed gender–and attracted great clerical opprobrium for it–which suggests these could certainly have been mixed-gender usage. And then, of course, there was the ultimate non-segregated latrine: simply peeing on the street. Because keeping streets clean was a considerable concern for medieval people (in contrast to the stereotype), we actually hear a lot about people fined for public urination in a back alley, or old wives’ tales about the horrors that result from peeing in the wrong place:
If someone pees against the wall of a monastery or in a graveyard, it would not be surprising if they are stricken by a seizure before their deaths. (Distaff Gospels, 15th century).
In the ancient classical world, group latrines were commonplace (multiple toilet openings in one room, as it were). Georgios Antoniou and Andreas Angelakis observe that there is no evidence for separate facilities by gender; however, on the basis of earlier research into the gendering of public and private space in ancient Greece, they suggest that women and men might simply not have used the room at the same time.
In conclusion, we can say gender-segregated toilets were first introduced in the mid-18th century. But the concept has a much longer and more fraught history.