Заедно с други български епископи през есента на 1203 г. изпраща писмо до папа Инокентий III с молба да им изпрати палиум (знак за пълномощията на духовния им сан):
„
Прекланяйки своите вратове под десницата на неговото господство като пред най-свети отец и господин папа, с наведена глава и подвити колена поклон. На първо място грешник и смирен митрополит на пресветата църква на Велбъжд Анастасий; след него грешник и смирен митрополит на великата църква на Преслав Сава и епископът, ако и недостоен, на пресветата църква на Богородица в Скопие Марин; смиреният епископ на пресветата епископия на Призрен Аврам; грешник и смирен епископ на пресветата църква на блажения и преславен великомъченик Прокопий в Ниш Кирик и недостойният епископ и грешник на пресветата църква на Богородица във Видин Климент — ние те молим най-смирено като единствен наш пастир и вселенски отец и господар да благоизволите да ни изпратите палиум за пълнота на свещенослужителския сан, та и ние през всичките дни на нашия живот да не престанем да се молим за вашето велелепие.
“
Анастасий Велбъждски получава специално писмо от папата, с което молбата му е удовлетворена. В отговора на папата велбъждския епископ е титулуван като Anastasio Arhiepiscopo Bellebusdiensi. В писмото си папата посочва:
До Анастасий Архиепископ Велбъждски... И тъй, понеже сметнахме, че нашият досточтим брат (Василий), търновският архиепископ, трябва да бъде поставен за примат във всички земи, в които заповядва най-скъпият в Христа наш син Калоян, сияйният цар на българите и на власите, като му предоставихме според обичая на апостолическия престол знаците на почит, които се отнасят до неговата длъжност, за да почетем и теб особено като уважаван член на Търновската църква и митрополит на Велбъждката църква и прелат по митрополитско право на нейните викарии, ние ти изпращаме по любимия син Л.[ъв], презвитер, кардинал на Светия кръст, легат на апостолическия престол, мъж за препоръчване поради честния нрав и учено дарование, когото обичаме с особена обич между останалите наши братя, да ти бъде даден според, формулата, скрепена и потвърдена с нашата була, палиум, сиреч знак за пълнота на първосвещеническа власт, взет от тялото на блажения Петър. И тъй ние напомняме на твое братство, подканяме те в Господа и ти поръчваме чрез апостолическо писмо да го приемеш смирено и предано и да си послужиш с него не за възвеличаване, а по-скоро за смирение вътре в църквата си през време на празничните дни на литургии, които ти посочи същият кардинал, и да се стараеш да се покажеш такъв, че вътрешната украса от добродетели да прозира под външната украса на одеждите и външната дреха да издава вътрешното състояние на душата, и то не с изкуствено преструване, а по-скоро с истинско изразяване.
“
Анастасий Велбъждки е споменат и в Бориловия синодик, съставен по решение на църковния събор през 1211 г. - като митрополит на Велбъжд „при благочествия цар Асен под властта на Търновската патриаршия“.[1]
.svg)