Genomics research is generating vast molecular sequence data ranging from single genes to whole genomes across an increasing number of species. However, fundamental difficulty in evolutionary studies emerges as the availability of sequences expands. Phylogenetics methods to reconstruct the evolutionary tree relating the sequences traditionally condition on a single, sometimes poorly estimated sequence alignment, where an alignment specifies which residues in the sequences derive from a common origin. This conditioning can cause bias and inappropriate infer in genomic studies, particularly when the sequences are highly diverse. For example, the early branching-order of Bacteria, Archaea and Eukaryotes, the three major domains of life, is troublesome to determine. As a solution, I describe a novel Bayesian model for simultaneously estimating alignments and the phylogenetic trees that relate the sequences. This sidesteps the bias issue inherent in sequential estimation. Joint estimation also allows one to model rate variation between sites when estimating the alignment and to use the evidence in shared insertion/deletions (indels) in the sequences to group sister species in the tree. I base this indel process on a Hidden Markov Model that makes use of affine gap penalties and considers indels of multiple residues. I develop a Markov chain Monte Carlo (MCMC) method to sample from the posterior of the joint model, estimating the most probable alignment and tree and their support simultaneously. I describe a new MCMC transition kernel based on the Forward-Backward algorithm and a careful choice of parameter marginalization that improves our algorithm’s mixing efficiency, allowing the MCMC chains to converge even when started from arbitrary alignments. Finally, my software implementation can estimate alignment uncertainty and I describe a method for summarizing this uncertainty in a single plot.