The relative complexity measure (RCM) is a new approach to evaluate relatedness of DNA sequences which eliminates the requirement to align sequences prior to analysis, a step required with standard reference methods. The value of the RCM approach to generate distance matrices for use in phylogenetic analysis of organisms has not been determined. This study compared RCM with the algorithmic and tree searching reference methods for phylogenetic analysis using fungal sequences. Sequences of the cytochrome b gene and the 18S rDNA gene were obtained from the GenBank database to determine feasibility of this method for phylogenetic relatedness. The RCM approach was also used to construct a phylogenetic tree using internal transcribed spacer (ITS) sequences from 23 medically relevant fungal species. The robustness of the RCM and reference approaches was determined by comparing the topology of seven medically relevant fungi within the phylogenetic trees generated after progressive removal of 10, 20, 30, 40 and 50% of the nucleotide bases from either the 5′ or 3′ end of the three genomic target sequences. The results demonstrated that the RCM method was equivalent to the reference methods for construction of phylogenetic trees from cytochrome b and 18S rDNA gene sequences. The phylogenetic tree constructed using the ITS sequence generated no contradictory topology. The RCM generated trees retained the appropriate topology after removal of up to 50% of the cytochrome b sequence, 40% of the ITS sequence, and 30% of the 18S gene target sequence. Comparatively, the reference methods failed to maintain topology after only a 10% sequence deletion for each genomic target. The results showed the RCM to be a reliable and robust computational approach for use in the construction of fungal phylogenetic trees without the requirement for prior sequence alignment.