From Wikipedia:
Cock and Bull
A pair of coaching inns alongside the former A5 road or the old Roman road Watling Street in Stony Stratford (Buckinghamshire, England), named respectively 'The Cock' and 'The Bull', are said to have given rise to the term "cock and bull stories." Coaches or the Mail coach would stop in the town on their way from London to the North and many a traveller's tall tale would be further embellished as it passed between the two hostelries, fuelled by ale and an interested audience. Hence any suspiciously elaborate tale would become a cock and bull story. This is a cock-and bull story in itself, however; as there is no evidence to suggest that this is where the phrase originated. The phrase, first recorded in 1621, may instead be an allusion to Aesop's fables, with their incredible talking animals. As this slightly predates coaching inns, the names of the two inns could have been a reference to "Cock and Bull stories" as to encourage the passing of such anecdotes within their doors.
Edit:
Having investigated further, I think Wikipedia is being a bit harsh. Saying that there is no evidence suggests that there is no Cock or Bull coaching inns in Stony Stratford. In fact there are, and have been for donkey's years. Indeed, every year Stony Stratford hosts a story telling event to celebrate this fact. Not only that, but Watling Street is a very famous road, though if you were stand on the London end of it, in Cheapside, you could be forgiven for not realising this, as it is little more than an alley there.
So what would count as further evidence? If there was a competing origin to the Stony Stratford version, I could understand, but to call the Stony Stratford Cock and Bull story a cock and bull story on the basis that there is no blue plaque commemorating the coining of the phrase, seems a bit harsh.