Fisher's randomization construction of hypothesis tests is a powerful tool to yield tests that are nonparametric in nature in that their level is exactly equal to the nominal level in finite samples over a wide range of distributional assumptions. For example, the usual permutation t test to test equality of means is valid without a normality assumption of the underlying populations. On the other hand, Fisher's randomization construction is not applicable in this example unless the underlying populations differ only in location. In general, the basis for the randomization construction is invariance of the probability distribution of the data under a transformation group. It is the goal of this article to understand the robustness properties of randomization tests by studying their asymptotic validity in situations where the basis for their construction breaks down. Here, asymptotic validity refers to whether the probability of a Type I error tends asymptotically to the nominal level. In particular, it is shown that the randomization construction is generally asymptotically valid for certain one-sample problems, such as for testing a mean or a median, even when the underlying population is not symmetric. In contrast, the randomization construction for two-sample problems may yield invalid tests, though it depends on the precise nature of the problem. For example, the two-sample permutation test based on sample means is generally asymptotically valid only if the samples are of the same size. When comparing medians, however, the two-sample permutation test is generally invalid even if the sample sizes are equal.