Hijo de Nascién y sobrino de Mordraín, que había sido el rey pagano de Sarraz; casado con Sarracinta; padre de Narpus. Tras convertirse al Cristianismo por influencia de José de Arimatea, Mordraín y Nascién se unen a la tarea de cristianización de Oriente llevada a cabo por aquél. La fe cristiana influye en gran manera en la vida de Celedonio. De hecho, este personaje posee algunos rasgos que indican una predestinación. Su mismo nombre tiene un significado específico: «el que es dado al cielo». Una sección completa de Estoire Saint Graal está dedicada a relatar las aventuras que le acontecen durante su juventud. Celedonio emprende diversos viajes por el Mediterráneo, en los que debe enfrentarse con los elementos de la naturaleza (tempestades), con diversos enemigos (piratas), y con las tentaciones que le envían los demonios. De todo ello sale con bien gracias a la protección de Dios. Finalmente, Celedonio viaja con su padre, Nascién, y su tío, Mordraín, a Bretaña, para reunirse con José de Arimatea, Josefés y sus partidarios, que estaban trabajando en la evangelización de Bretaña, y que habían sido víctimas de persecución por parte del rey pagano de Norgales, llamado Crudel, del que son prisioneros José de Arimatea y su gente. Mordraín reúne un ejército y ataca a Crudel; en la batalla, el rey de Norgales es vencido y muerto, y Nascién propone a su hijo Celedonio como sucesor del pagano. De este modo, Celedonio se convierte en el primer rey cristiano de Norgales. En Queste, se dice, sin embargo, que Celedonio es rey de Escocia.