Here is some evidence that dogs have been associated with humans for as long
as 135,000 years (since hunter-gatherer times).

From the New Scientist online magazine:

New tricks and old dogs

Canine remains at human burial sites led researchers to suspect that dogs
became domesticated around the time that our nomadic hunter-gatherer
ancestors settled down to grow crops, around 14 000 years ago, long before
we acquired goats, cattle and sheep. But in 1997, Carles Vilá and
researchers in Robert Wayne's lab at the University of California at Los
Angeles blew this idea wide open.

They compared mitochondrial DNA from 67 breeds of dogs with that from
wolves, coyotes and jackals. The studies revealed at least four separate
lines of descent from dogs back to wolves, showing that there were at least
four successful attempts to domesticate them. The real surprise, though, was
the high level of genetic variation between different breeds. "The
mitochondrial DNA data suggest very clearly that the diversity found in dogs
might have an origin much older than 14 000 years," says Vilá. Knowing the
rate at which these DNA sequences change, he estimated that the split with
wolves--and hence domestication--occurred around 135 000 years ago.

If this is right, domestication started at around the time that our own
species evolved, and perhaps not long after our ancestors acquired language.
Pet ownership could well pre-date such cultural mainstays as art and the
practice of burying the dead. But even Vilá, now at Uppsala University in
Sweden, accepts that the date is controversial. Wayne hopes new research
will pin it down. "We are examining ancient breeds, such as the Xolo,
ancient remains from the Middle East and South America of the earliest dogs
and nuclear genetic markers," he says.
---------------------------
For the associated article, see:

http://www.newscientist.co.uk/features/features.jsp?id=ns22281

Enjoy!

laurie              Colorsplash Farm              Apex NC, USA
                      (...and Tigris Mastiffs)