Cats traveled with humans, including to ancient Egypt and Europe, where they served as mousers and were even worshipped.