Muscle tissues can be divided into six classes; smooth, fast skeletal, slow skeletal and cardiac muscle tissues for vertebrates, and striated and smooth muscle tissues for invertebrates. We reconstructed phylogenetic trees of six protein genes that are expressed in muscle tissues and, using a newly developed program, inferred the phylogeny of muscle tissues by superimposition of five of those gene trees. The proteins used are troponin C, myosin essential light chain, myosin regulatory light chain, myosin heavy chain, actin, and muscle regulatory factor (MRF) families. Our results suggest that the emergence of skeletal-cardiac muscle type tissues preceded the vertebrate/arthropod divergence (ca. 700 MYA), while vertebrate smooth muscle seemed to evolve independent of other muscles. In addition, skeletal muscle is not monophyletic, but cardiac and slow skeletal muscles make a cluster. Furthermore, arthropod striated muscle, urochordate smooth muscle, and vertebrate muscles except for smooth muscle share a common ancestor. On the other hand, arthropod nonmuscle and vertebrate smooth muscle and nonmuscle share a common ancestor.