A major obstacle in the development of an HIV vaccine is the formidable mutational capacity of the virus. This rapid rate of mutation allows the virus to quickly adapt to the adaptive immune response, making priming of the immune system via vaccination an as yet futile effort. In this talk, I will present some graphical models we have developed for inferring patterns of immune escape in HIV evolution. These patterns turn out to be remarkably consistent, revealing details of the the immune response against the virus as well as evolutionary constraints within the virus. Using these apparent constraints on viral evolution, we are beginning exploration of new vaccine candidates and hope to better understand the underlying mechanism of the disastrous Merck vaccine failure this past September.