Просто продвигайся по сюжету до прихода в Нью-Вегас. Не страшно, если ты убивал легионеров и имеешь дурную репутацию у Легиона. В городе к тебе подойдет фрументарий Цезаря Вульпес Инкульта, сообщит что они следят за тобой и даст "знак Цезаря" гарантирующий прощение от прошлых преступлений и беспрепятственный проход. Идешь Коттонвуд-Коув и садишься на лодку до Форта, там говоришь с Цезарем, который дает тебе задание взорвать бункер с протектронами Мистера Хауса, выполняешь его и тебе предложат вступить в Легион Цезаря.