late 14c., "indestructible, unable to be loosened," also figuratively, of problems, etc., "incapable of being solved or explained," from Old French insoluble or directly from Latin insolubilis "that cannot be loosened," from in- "not" (see in- (1)) + solubilis "that can be loosened" (see soluble).
It was a tacit conviction of the learned during the Middle Ages that no such thing as an insoluble question existed. There might be matters that presented serious difficulties, but if you could lay them before the right man -- some Arab in Spain, for instance, omniscient by reason of studies into the details of which it was better not to inquire -- he would give you a conclusive answer. The real trouble was only to find your man. [Gertrude Bell, "The Desert and the Sown," 1907]
Meaning "incapable of being dissolved in a liquid" is from 1713.