Changes in intestinal microbial diversity and community structure have been associated with clinical disease. Restoration of the gut microbiome to a “healthy state” is an emerging approach for addressing gastrointestinal tract related diseases. Therefore, accessing changes in gut microbiome composition characterized through various sequence-based methods may have profound health implications. Current computational methods for comparing microbial communities, such as UniFrac, are usually based on multiple alignment and phylogeny, making them impractical or prohibitively time consuming for use in clinical assessments. Thus, we developed a simple and accurate method, compression-based distance (CBD), supporting the efficient analysis of the similarities and differences between microbial communities. CBD takes advantage of the fact that compression algorithms make use of repetitive data for more efficient data storage and uses the relative compression of combined and individual datasets to quantify overlaps between two microbial communities. CBD is designed to utilize even modest numbers of sequence reads obtained from various sequence-based methods. CBD operates directly on the original sequence data instead of requiring multiple alignment and phylogeny, thus omiting the need for expert intervention in aligning sequence reads. V2 and V6 16S rDNA sequence information of gut microbiome (Turnbaugh et al.) was used to validate the utility of CBD to distinguish various gastrointestinal tract microbiomes. Sixteen out of sixteen comparisons using CBD analysis were consistent with those from the in-depth analysis by Turnbaugh et al. demonstrating that CBD gave similar results as the in-depth analysis. Thus, CBD provides a simple and accurate method for assessment of gut microbiome composition.