 Felix, in company with John, set out for Rome in the depth of winter and arrived there in January 1198, the beginning of the pontificate of Innocent III.They had letters of recommendation from the Bishop of Paris, and the new pope received them with kindness and lodged them in his palace.Innocent III, though little in favor of new orders, granted his approval to this enterprise in a Bull of 17 December 1198, under the named of the Order of the Holy Trinity for the Redemption of Captives.