Pretty sure primeval canines didn't behave that much differently than the ones we have today: they attach themselves to anything that feeds them.
That's not just a canine trait. That's pretty much the original basis for taming animals of any kind.
Minor ramble:
First it begins on an individual level, where a single animal is tamed. With most creatures the process ends here as it is difficult to reliably duplicate and cannot be perpetuated long enough to supply a breeding pool. Prestige animals like tame lions etc come here (a surprising number of animals can be tamed).
The second 'tier' (for lack of a better word) concerns animals that can be somewhat reliably tamed, and who can be usefully trained to work with humans sometimes, but still retain some wild characteristics (often varying noticeably from individual to individual). These animals straddle the line between tame and domesticated, the most important thing being that these animals are not dependent on humans in any way. They might
like us and get along with us, but their full naturally-occurring skill haven't been bred out yet. Elephants are a decent example here.
The final tier is full domestication (distinct from mere taming), where a species lives in symbiosis with humans (lopsided at times, but symbiosis nonetheless) and both species depend on each other or at least desire the benefits the other offers.
Food is a huge enabler. If a human becomes a reliable source of food and the animal is reasonably intelligent, the animal will recognise that it's stupid to kill the 'golden goose' - simple evolution, that. The animal may also place a human that gives it food in the same mental category as 'parent' or 'pack leader'. Food, especially tasty food that can be obtained reliably is something that speaks to animal brains at a very deep level. It is an extremely simple way of communicating, and one of the few common grounds that are both effective and nearly universal.
Second minor (unrelated) ramble:
One thing I've wondered about dogs is whether or not they started from a very small pool of particularly social wolves that spread (possibly even becoming a trade good), or if the wolf-becomes-dog phenomenon is common enough that it arose many times throughout history.
The question sounds stupid at first because dogs seemed to arise all over the world, but then, that was believed of humans too at one point. More importantly, domestic cats have actually been traced to an incredibly small number (possibly as small as six original animals) of highly social progenitors*.
*
This genetic research brought to you by the fact that domesticated cats cannot taste sweet tastes. I shit you not. : Food is massively important to interspecies communication, taming is distinct from domestication, and housecats are descended from a very, very small number of animals.