We have developed a computational technique referred to as complex phylogenetic profiling. Our approach combines logic analyses of gene phylogenetic profiles and phenotype data. Logic analysis of phylogenetic profiles identifies sets of proteins whose presence or absence follows certain logic relationships. Our approach identifies phenotype specific logic, i.e. it identifies sets of proteins simultaneously present or absent only in genomes with a given phenotype. For example, for most genomes expressing phenotype A, the presence of protein C presumes the presence of protein B, while for other genomes (not expressing phenotype A) the presence of protein C presumes the absence of protein B. Application of complex phylogenetic profiling to bacterial data and several well studied phenotypes reveals genotype-phenotype associations on the level of fundamental biochemical pathways.