I have heard this phrase quite a few times and I am curious what is the origin of this phrase?
etymonline tells us:
late 15c., "fish-like, slimy," from fish (n.) + -y (2). In reference to taste, from 1540s. Sense of "shady, questionable" is first recorded 1840, perhaps from the notion of "slipperiness," or of giving off a bad odor.
So it either refers to the tendency of fish to be slippery, meaning they cannot be trusted to not slip out of your hands, or it refers to the notion that fish tend to start smelling after a while.
Since we also use the expression that something smells fishy, I would assume that the odour-link is the most likely: fish, and places where fish is sold, tend to be associated with bad smells.