The trope of the unlucky fisherman who pulls out an old shoe or boot can be found in a classic Arabic folktale called "The Slippers of Abū al-Qāsim al-Tanbūrī", which remains popular today (see Rooke, 2020). In the version of the tale published in France in 1770 by Cardonne, a rich miser from Baghdad called Abu Casem owns a pair of dilapidated slippers that he refuses to give up. One day, he goes to the public bath and borrows by accident the brand new slippers of the Caliph. Accused of theft, Abu Casem is thrown in jail and freed after paying a fine. The miser takes revenge on his trash-worthy slippers by throwing them in the Tigris. A fisherman pulls them out by mistake, and, finding that the slippers' nails have damaged his net, he angrily returns them to the miser, launching them through a window in the miser's house, where they land on precious objects. The rest of the tale consists in the increasingly desperate (and amusing) attempts of the miser at getting rid of the slippers: not only they always get back to him, but he gets in trouble every time, ending in jail and paying heavy fines.
Is this tale the ur-version of the old boot fishing trope in Western media? It is difficult to say. On the one hand, the fisherman plays only a small part in the story and he is not central to it. Also, he uses a net and is not an angler. On the other hand, he does fish out a dilapidated shoe, and he is not happy about this, which is characteristical of the trope. The Abu Casem story was always popular in the West, and was (and still is) often included in the One Thousand and One Nights collection (whether it belongs to it is disputed). We can find versions of it in books and popular magazines for adults and children in Europe from the 18th century to this day (see Noble, 1831 and Robertson, 1876). It was the main inspiration of August Strindberg's play Abu Casem’s Slippers in 1908 (Rooke, 2020). So, even if the tale was not a direct inspiration for the trope, it is possible that it participated in the construction of the latter in the popular media. It also shows how fundamentally comedic is the scene of the fisherman fishing out an old shoe: the Arab and Persian storytellers were probably having their audiences in stitches when they came to this part of the tale.
Now, when it comes to the problem of shoes in fishing areas, it is certain that 19th- and 20th-century westerners were not particularly environmentally mindful of their waterways, and that they did throw a lot of refuse in it, including old shoes and other products of the industrial revolution. The hygienists of the 19th century struggled with containing the garbage in the cities and finding out ways to make people get rid of their trash in a civilized way.
In 1880, the largest of the basins of the Tuileries Garden in Paris was cleaned up. The workers emptied the water, captured the fish, and carried away cartloads of mud and silt. And then (La Petite Presse, 25 March 1880):
A quantity of various objects, such as old shoes, small boats, knives, and up to two woman's buns were uncovered when the water was expelled from the basin.
And not just in Paris. In 1884, Dr Descaine, in an article about public health, mocked the advertising in the brochures for spas and health resorts (La France, 1 April 1884).
We are told of the limpid and shady course of a river open to the pleasures of fishing, which is often only a narrow stream, always changing, wet only on rainy days, and in whose bed abound, by way of fish, old shoes, broken bottles, etc.
In the late 19th century, English author, illustrator, and traveller Charles George Harper was of similar opinion when describing the English countryside, and offered us this beautiful rant in 1893:
I prefer the paintings to the photos, because, although I have a happy liking for realism and truth, I draw the line at the camera's uncompromising rendition of battered tin cans, broken crockery, fish offal, old boots, and other unpicturesque and sordid objects that lazy house wives cast out of window into the water.
Sad, indeed, is the state of the picturesque stream or romantic glen that borders upon a camp of civilisation, for abundance of old boots and sardine tins are the reward of the diligent botanist or natural historian in these gates ; bracken grows not more profusely than are strewn the shards and potsherds of the neighbouring town. But no matter how frequent and plentiful the wreck and refuse in the matter of bottomless kettles, superannuated umbrellas, and broken dishes, the Old Boot is the commonest object of the seashore, highway, by-way, lane, or ditch - no mountain too high, no valley too deep for it to be found. The angler lands it with language and dashed expectations from the trout stream ; the trawler finds it unaccountably in his trawl-net when he returns from the bay ; the ploughman disinters it from the field ; and children dig it up from the sands: everywhere is the Old Boot. I have communed with Nature, and rambled amid the wildest and loneliest of scenes, when my meditations have been arrested by old boots, and at once the poetry and romance of the scene have flown away. Truly, there is nothing like leather.
Harper was something of a satirist, so it may be possible that the English countryside and its waterways were not literally littered with old boots. However, his text is contemporary of the early efforts at environmental preservation undertaken in Britain in that period. The link between the river boot, as a symbol of pollution, and the proto-environmentalism of late 19th Britain would be worth exploring.
But did fishermen, or more properly anglers, actually fish old shoes? Information is scarce, as expected since this is not something people would be proud of. British traveller Cecil Roberts told in 1891 the following story, which may have happened in the 1870s near the Mississippi river.
I went down to the river, and having heard that catfish were not at all particular in the matter of bait, I dug some worms, of which there were plenty to be had with little trouble. Baiting my hook I threw it into a hole that promised well for a bite. However, after some minutes, feeling no pull I started to haul my line in, but found I was snagged. "My luck again," said I, "hooks and dinner gone at one fell swoop, and not a red cent to buy any more with." Hauling gently, however, first one way and then another, I felt the thing I had hooked first move and then come slowly away. So pulling gently for fear of snapping the line I at last landed it. When I got hold of the thing I found it was an old boot full of mud. Taking and washing it I found it was a right foot boot and in fairly good order, much better than mine was, so I tried it on and finding it was a good fit, I put it on and threw my own away. I fished for some time longer and at last I caught a good sized cat fish.
This is comedic, of course, which does not make it false.
In the late decades of the 19th century, it seems that the trope was already well established. The "Old fisherman" joke (1892) is about an old, rugged-looking angler who describes pedantically how he can tell a fish species by the way it bites, until his catch comes to the surface: "It was an old boot". An article published the same year in the English Fishing Gazette tells its readers that the author "caught nothing, not even an old boot". A somewhat longer version of the joke can be found in novel form in the book of short stories The Spoopendyke Papers, by American author Stanley Huntley (1883). There is also a humorous poem by French author Franc-Nohain, who tells that he was invited as a teenager in a house where there was a painting of an angler fishing out an old shoe, "with the disappointment written all over his face" (Franc-Nohain, 1899).
But it was indeed in the visual arts that the trope flourished, and the earliest example I've been able to find is from 1880, described here as follows:
A fisherman is in the act of pulling out a big fish, which the attending small boy reaches out to take in with a dip-net, when the fish turns out to be only an old shoe.
However, this is not a painting or a drawing: it is done in the sacred art of ornemental taxidermy (made semi-famous by Steve Carrel in Dinner for Schmucks, 2010), and the fishermen are taxidermied frogs. A picture of this extraordinary object is kept at the Smithsonian (on the left, it's tiny, and the boot is barely visible).
Another example of early visual display of the shoe trope is this contraption (1887) called a "mechanical window-piece" (I'm not sure of the mechanical aspect). The ad copy says:
The "Lone fisherman" is as comical as it is suggestive, for we have all "been there". After many fruitless attempts to catch a fish, an old boot is at length drawn up, but this does not seem to check the ardor of the fisherman.
Whether or not "we" had actually "been there" is perhaps irrelevant: once it was put in image form the trope was here to stay, not unlike the contemporary drunk-leaning-on-a-lamp-post imagery. By the turn of the century, such images were everywhere in the form of humourous postcards, such as this happy boot fetishist, these angling buddies of 1904, or these babies of 1905 photographed by Anne Geddes.
->Sources
I am not going to be able to give a source or a textual origin to the trope of fishers pulling up leather footwear by their hooks. What I, however, can attempt to answer, is how this stereotype might have come to be, from an archaeological perspective. Now, this answer is going to be at least partially anecdotal, so if the mods find it lacking the expected rigor, I apologize in advance.
Leather footwear is a category of archaeological artefacts that keeps exceptionally well in wet conditions, much more so that many other organic remains, particularly if they are covered by, for instance, silty soils, creating anaerobic conditions (which is always good for preservation in general). Silt (a category of fine sediments, with a grain size between that of very fine sand and clay) often constituting a majority of the soils found at the bottom of lakes, habours, channels and rivers - that is, places where fishing are often found to take place.Leather footwear is often made from thicker, sturdier types of leather, particularly the soles (in periods where footwear had distinct soles) often comprises more than one piece of stacked leather, and if the footwear has heels, these can consist of many pieces of thick, stacked leather. The composition of the sturdy leathers and how the footwear is assembled, might go some way, in explaining their state of preservation.
Within city-, and certain wetland-, and wetter settlement archaeological contexts, leather footwear is one of the most abundant type of finds, after such things as ceramics, glass, and bone (animal, for the most part), and in some instances wood (though this often in the form of larger building materials; water pipes, foundational pillars and its like). What then perhaps, in reference to the question, sets leather footwear apart from these other types of finds, might be the ability to be more easily caught by a fishing hook, due to their size and the softness of the leather, while they remains strong enough not to fall entirely to pieces in the process of hauling them in.
To put things a little into perspective, during excavations carried out in Copenhagen, Denmark, when the stations for the new metro-ring where being established (The tunnels themselves being bored out far beneath any man-made contexts) around 7000 whole and partial leather shoes and boots, from between the 1300s and the 1800s, were found (1) from the three stations situated within the borders of “old” Copenhagen. This fits very well with my own experience from archaeological city excavations, where leather footwear is often abundant in the, several meter-thick, layers of human occupation, compared to other organic categories.
Not so long ago, and perhaps more relevant to the present question, during marine habour excavations, and these seldom less than some 100 meters from land, leather shoes and boots were one of the most plentiful type of finds we did – from relatively recent Doc Martens to 16th century loafers.
To avoid this becoming too anecdotal, another striking example of leather footwear preservation, is the ongoing excavations of the roman fort and settlement of Vindolanda (in connection with Hadrian’s Wall in northern England). Out of 7000 leather artefacts found, 4000 are footwear (2). Roman Footwear. 1700-year-old footwear! Now, tell me that isn’t cool as f**k.
If we dwell on England for a bit, excavations from York, can muster approximately 400 parts of leather footwear, the by far richest assembly of leather artifacts found here, only leather waste and scraps being more plentiful (3).
Another appropriate example, being the many, new and old, pieces of leather footwear being found by so-called Mudlarkers (archaeological hobbyists), scavenging the shores of the river Thames for old artefacts. This fellow (4), gives a pretty good impression, of the preservational durability of leather footwear in waterlogged conditions by the Thames.
Shoes and boots are plentiful in waterlogged or wet areas in close proximity to human settlements, and they can keep fresh in these conditions for a very long time, while still being caught on a hook and hauled up in a somewhat assembled condition.
I hope this answer might give a tentative explanation, as to how the trope of old boots on fishing hooks might have come to be.
Edit: I had misremembered details about, which stage of the metro-excavations in Copenhagen, the footwear was from. Doesn't change much, really, just nice to be accurate.