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. Innocent appointed John of Matha superior-general and commissioned the Bishop of Paris and the Abbot of St. Victor to draw up for the institute a rule, which he subsequently confirmed. Felix returned to France to establish the order. He was received with great enthusiasm, and King Philip Augustus authorized the institute in France and fostered it by signal benefactions.