While it may seem that horses and dogs are very different, a deep dive into their family tree shows them to be related. They had a common ancestor about 55 million years ago.