The first
well-documented condom was created by Gabriel Fallopius (yep, as in fallopian tubes. He was an
anatomist) in the mid 1500s. They were made of medicated
linen, a standard of 8 inches long (I won't comment on that.) and was tied on with a
pink ribbon. I have no idea why it was pink. More
feminine, perhaps? They were referred to as "
overcoats".
From here, legend has it that there was an Earl of Condom (who, needless to say, later went on to request that his name not be associated with his invention) that was asked by King Charles II to create a device that would prevent him from getting syphilis. As there were many, many bastards of this particular King, it was obvious that contraception was not his main goal. Anyway, the device was made of oiled and stretched sheep's intestine.
In the 1870s, they first started being made from vulcanized rubber, and almost immediately aquired that nickname. Latex wouldn't be used until the 1930s.