The story
From mince (“to say or utter vaguely (not directly or frankly)”, transitive figurative verb) + words. First attested in the mid-1500s.
Etymology from Wiktionary, CC BY-SA 4.0.
mince words
Today it means: To restrain oneself when speaking by withholding some comments or using euphemisms in order to be polite, tactful, etc. Full definition →