Separability is an attractive feature of covariance matrices or matrix variate data, which can improve and simplify many multivariate procedures. Due to its importance, testing separability has attracted much attention in the past. The procedures in the literature are of two types, likelihood ratio test (LRT) and Rao's score test (RST). Both are based on the normality assumption or the large-sample asymptotic properties of the test statistics. In this paper, we develop a new approach that is very different from existing ones. We propose to reformulate the null hypothesis (the separability of a covariance matrix of interest) into many sub-hypotheses (the separability of the sub-matrices of the covariance matrix), which are testable using a permutation based procedure.We then combine the testing results of sub-hypotheses using the Bonferroni and two-stage additive procedures. Our permutation based procedures are inherently distribution free; thus it is robust to non-normality of the data. In addition, unlike the LRT, they are applicable to situations when the sample size is smaller than the number of unknown parameters in the covariance matrix. Our numerical study and data examples show the advantages of our procedures over the existing LRT and RST.