We’re told that certain diseases (STDs, for example) can only be contracted by coming into contact with an already infected person.
If that really is the case, how did these diseases get started in the first place?
From bacteria and virus that mutated into new forms*. If a bacteria doesn’t cause ill effects, it can be passed on and no one notices. Suddenly it mutates - say a protien folds differently and causes its host to feel ill and whammo! It’s now a pathogen. If this mutation has the side effect of encouraging that virus or bacteria to reproduce (say, the host body has no antibodies against it, so can’t kill it quickly,) or spread to other hosts (perhaps it makes the host body sneeze mucusy, wet sneezes, which the virus travels in to find a new host) then it can become a successful pathogen pretty quickly.
Many bacteria and some viruses, however, die pretty quickly outside of a body. So in order to be infected, you have to have direct contact with a person or their fluids (snot, spit, semen, blood - depending on where the pathogen likes to hang out) to pick up their pathogens. You wouldn’t pick up HIV from a bookshelf, for example, because it simply won’t live there.
*If you’re anything like my kid, your next question will be: “But where did THAT bacteria or virus come from?” The primordial soup, kiddo. They’re the simplest forms of life, and a few protiens that wound around each other and did this weird thing where they starting making copies of themselves - the earliest life probably was something we’d call a bacteria.
What I’m getting at is that the first person to catch a communicable disease must have got it through some other method than coming into contact with someone who already had it (e.g. through mutation of another bacteria). Therefore contact with an already infected host is not the only way of getting one of these diseases.
No, but it’s the only way of getting a disease that exists, that has a name already. Mutation implies first victim status, and so yes, that would, by definition, not have been caught from anyone. It also doesn’t happen very often - there are probably a few thousand pathogens, a few dozen of which are common. Compared to the millions of humans and other animals that have lived on the Earth since the beginning of Life, that’s not many mutations that have been successful.
Antibiotic-resistant bacteria are a different matter. Misuse of antibiotics has indeed caused the mutation survival rate to increase in the last 100 years, and there are some nasty things happening as a result. Most of the mutations, however are not significant enough to warrant a new label as a new form of bacteria, but merely an “antibiotic-resistant” label in front of their name. But that a whole 'nother thread.
You might have a bacteria that mutates to cause a new illness, called Nisse’s Disease. I then might get Nisse’s Disease from you, but the chances of my bacteria mutating in the same exact way to cause the same exact bacteria strain independently are astronomically small. So if I never came into contact with you or your future infectees, I could pretty safely assume I’d never get Nisse’s Disease.
Well, I figure one of your intestinal or skin flora could mutate at any time and you would therefore be the very first person to be infected with a brand new disease. In that case, no contact with anyone else would be needed.
A side note: some infections also can spread by aerosolization, in which case the only contact needed would be with air the patient coughed or breathed. And some can also be spread by fomites, items that have been contaminated with bugs by contact with the patient. The individual characteristics of the germ involved determine how well it survives outside the body.
That’s like saying “The first human in the world must have come from something other than a human (e.g. mutation from another primate), so getting a female human pregnant is not the only way to create a human baby.”
WhyNot appears to given the scientifically observed answer to the OP, so we get to post alternative answers now.
So, the diseases might be designed by the Intelligent Designer. A new disease could be created at any time by this method. Bubonic plague, AIDS, smallpox, West Nile disease, and so on.
Baby… Baby, calm down… I don’t care what the doctor said… You must have mutated a de novo strain of gonorrhea yourself from some previously harmless bacterium already present in your cooter. I swear!
Or the Intellegnet Designer could cause a mutation to occur - I don’t think the two ideas are mutually exclusive. 
The Coming Plague has a ton of information on how plagues start and sustain themselves. It was assigned reading for one of my university roommate’s epidemiology classes, and my girlfriend’s microbiology class too. A book I read recently that covers some of the same ground is Virus X. He has an interesting idea on the relationship between viruses and their hosts. Less authoritative but entertaining, while providing a primer on the basics, are the books by Richard Preston, of Hot Zone and Demon in the Freezer fame.
Just because Calvin Klein uses Kate Moss so often in ads, why do you feel he is so intelligent? And why would he create diseases?