In this article, I describe the puzzle of idiomaticity in native and non-native uses of English: why are idioms so resistant to acquisition, even by advanced leaners and users of English? I identify the main cause of this problem in the “idiomatic paradox”, whereby the very reasons which make idiomaticity so natural and necessary in native-speaker discourse are precisely the reasons non-native speakers find them so elusive. I look at some of the implications of of the idiomatic paradox for language teaching and the use of English as a Lingua Franca.