Dogs are often considered as man's best friend. However, the aforementioned phrase has a certainly negative meaning. The same phrase exists in French as well.
Other negative phrases with dogs include work like a dog, die like a dog, a dog's life, etc. How long ago in the English language does this negative connotation date?
Yours is an interesting question but, as explained in the previous answers and comments, since dogs were considered wild and possibly dangerous animals till a few centuries ago, I think that probably the issue is: when did expressions about dogs change from negative to neutral or positive?
The first linguistic oddity to do with dogs concerns where the word 'dog' came from. The name was preceded by the perfectly good Anglo-Saxon word 'hound', which was also used in other European languages. 'Dog', in common with several other animal names ending in 'g', like frog, hog, pig and stag, seems to have been coined around the 13th century for reasons that no one is at all sure about.
Prior to the 18th century, dogs were kept for hunting and defence and not as pets. The only deviation from that rule was that of the derided 'lap-dog', which John Evelyn recorded in his Diary, circa 1684, as a dog fit only for ladies: Those Lap-dogs had so in delicijs [delight] by the Ladies - are a pigmie sort of Spaniels. Lap-dogs apart, the phrases used to refer to dogs in the 16th and 17th centuries indicate their image as being vicious and disease-ridden:
Hair of the dog that bit you, first used in 1546 as a reference to rabies.
Cast someone to the dogs, 1556. Dog in the manger , 1564
If you lie down with dogs, you will get up with fleas, 1573 The dogs of war, 1601
Go to the dogs, 1619
Also, phrases that indicate the treatment of dogs show that they were considered to be of little worth:
Lead a dog's life (1528) Not fit for a dog (1625) As sick as a dog (1705)
The unfortunate mutts were considered so beyond the pale that dog hangings, as punishment for chasing sheep or whatever else dogs did naturally, were commonplace. The phrase 'give a dog a bad name', 1705, was originally 'give a dog a bad name and hang him'.
The language relating to canines took a turn for the better later in the 18th century.
The first example in print of the term 'dog-basket' dates from 1768. The need for a name for a piece of furniture provided specifically for the comfort of dogs shows a clear turning point in attitudes towards them. This shift in outlook continued steadily and in 1823 we first find 'dog biscuits', followed in 1852 by 'dog show'. By the mid 20th century we find clear linguistic evidence that a dog was to be considered almost on a par with humanity - 'dog-sitter' (1942).
The greatest claim to fame of Warrensburg, Missouri is that it is where the phrase 'a dog is a man's best friend' originated. In 1870, a farmer shot a neighbour's dog and, in the subsequent court case where the owner sued for damages, the lawyer George Graham Vest gave a tear-jerking speech that became known as the Eulogy to a Dog:
Source: The Phrase Finder
Dogs were not always regarded so highly. Yes, they were a great help to early man (and remain so today), but they weren't elevated to the position of "man's best friend" until relatively recently.
I don't know how long ago the comparison was first made between someone low and a dog, but it must have been a long time ago. In The merchant of Venice (Act I, Scene III), Shylock states
You call me misbeliever, cut-throat dog,
And spit upon my Jewish gaberdine,
And all for use of that which is mine own.
Well then, it now appears you need my help...
And foot me as you spurn a stranger cur...
You call'd me dog; and for these courtesies
I'll lend you thus much moneys'?
Much earlier, in the Bible,
Then Abishai son of Zeruiah said to the king, “Why should this dead dog curse my lord the king? Let me go over and cut off his head.” (Samuel)
... it is a safeguard for you. Watch out for those dogs, those evildoers, those mutilators of the flesh. (Phillipians)
From the above, I would guess that as long as there were skulking dogs, there have been such comparisons made.
According to the OED, "hound" is an older word than "dog" in English. The earliest cited use of hound to refer to a person in a derogatory way is from the year 1000. Others from 1290, 1340, etc. By that time, "dog" was being used in the same way.
Now this, prompted by @medica answer: As the Bible was translated into English, the instances of the Jewish use of "dog" as the word appears in English translation began to be known among English-speakers. (Think: Shakespere and then printing press). The influence of the English bible on the vocabulary of English-speaking people can hardly be overstated. And the usages in English translations of scripture (here I include 2 of approx 40, including the "messianic" Psalm 22 ("For dogs have compassed me: the assembly of the wicked have inclosed me") and Matthew 7:6 "give not that which is holy unto dogs") became famous and iconic. I will note that the usage in Job is not derogatory, as it refers to a shepherd dog.
