The word stems from an old Bavarian term for “hard”; either referring to the process used to grind the grain into flour, or the density of the final bread product. According to Langenscheidts Taschen Wörterbücher (1956), it refers to a form of “pumping work”. The philologist Johann Christoph Adelung states that the word has an origin in the Germanic vernacular where pumpern was a New High German synonym for being flatulent, and Nickel was a form of the name Nicholas, commonly associated with a goblin or devil (e.g. "Old Nick", a familiar name for Satan), or more generally for a malevolent spirit or demon. Hence, pumpernickel means "devil's fart", a definition accepted by the publisher Random House, and by some English language dictionaries, including the Merriam-Webster Dictionary. The American Heritage Dictionary adds "so named from being hard to digest". A variant of this explanation is also given by the German etymological dictionary Kluge that says the word pumpernickel is older than its usage for the particular type of bread, and may have been used as a mocking name for a person of unrefined manners ("farting Nick") first. The change of meaning may have been caused by its use as a mocking expression for the (in the eyes of outsiders) unrefined rye bread produced by the Westphalian population.
The Oxford English Dictionary does not commit to any particular etymology for the word. It suggests it may mean a lout or booby, but also says "origin uncertain". The OED currently states the first use in English was in 1756.
A false folk etymology involves Napoleon, who, while invading Germany, asked for bread and was served dark Westphalian rye. According to the folktale, Napoleon declared that this was not suitable bread for himself, the emperor, but was bread (pain) for Nickel (or Nicole), his horse: "C'est du pain pour Nickel/Nicole!" In a variation of the same basic story, Napoleon declared that the bread was no good for him, but was only good (bon) for his horse: "C'est bon pour Nickel!" The name "Nickel" is not confirmed for any of Napoleon's many horses. Additional folk etymology grew from a "witty interpretation", proposed by seventeenth-century satirist Johann Balthasar Schupp, that the bread was only good for "Nicol", a nickname for a weak or puny horse.