The story
From the London, England fishmarket Billingsgate: "Billingsgate is the market where the fishwomen assemble to purchase fish; and where, in their dealings and disputes they are somewhat apt to leave decency and good manners a little on the left hand." (Dictionary of the Vulgar Tongue, 1811).
Etymology from Wiktionary, CC BY-SA 4.0.