Phenylalanine and tyrosine ammonia-lyases form cinnamic acid and p-coumaric acid, which are precursors of a wide range of aromatic compounds of biotechnological interest. Lack of highly active and specific tyrosine ammonia-lyases has previously been a limitation in metabolic engineering approaches. We therefore identified 22 sequences in silico using synteny information and aiming for sequence divergence. We performed a comparative in vivo study, expressing the genes intracellularly in bacteria and yeast. When produced heterologously, some enzymes resulted in significantly higher production of p-coumaric acid in several different industrially important production organisms. Three novel enzymes were found to have activity exclusively for phenylalanine, including an enzyme from the low-GC Gram-positive bacterium Brevibacillus laterosporus, a bacterial-type enzyme from the amoeba Dictyostelium discoideum, and a phenylalanine ammonia-lyase from the moss Physcomitrella patens (producing 230 μM cinnamic acid per unit of optical density at 600 nm [OD600]) in the medium using Escherichia coli as the heterologous host). Novel tyrosine ammonia-lyases having higher reported substrate specificity than previously characterized enzymes were also identified. Enzymes from Herpetosiphon aurantiacus and Flavobacterium johnsoniae resulted in high production of p-coumaric acid in Escherichia coli (producing 440 μM p-coumaric acid OD600 unit−1 in the medium) and in Lactococcus lactis. The enzymes were also efficient in Saccharomyces cerevisiae, where p-coumaric acid accumulation was improved 5-fold over that in strains expressing previously characterized tyrosine ammonia-lyases.