Natural Language Understanding has witnessed a watershed moment with the introduction of large pre-trained Transformer networks. Despite impressive performance on NLU tasks including Natural Language Inference (NLI), we find that pre-trained transformers are invariant to random word order permutations---i.e., they assign permuted examples the same labels as their non-permuted counterparts. This issue is present for pre-Transformer encoders as well and holds in both English and Chinese. Furthermore, we find that models are even able to correctly label permutations of examples that they initially failed to predict correctly. We propose a suite of metrics to measure the severity of the issue and investigate which properties of particular permutations lead models to be word order invariant. Our findings lead us to question whether our current models have learned anything akin to a human-like understanding of syntax.