楚地自古崇尚巫风，直至隋代，其习犹故。荆州是关羽一生事业的顶点，也是他功败垂成之地。南北朝时期，江陵城内出现了一位十分灵验的“城隍神”，这位城隍神便是曾经修筑坚固江陵城的关羽。关公信仰的中心地区曾经过四次大范围转移：第一次是隋唐时以玉泉寺为中心的荆楚地区；第二次是北宋以解州为中心的山陕河洛地区；第三次是元明清以京师为中心的华北地区；第四次是明代中叶以“抗倭”为标志的江浙闽广地区。

隋文帝开皇十三年（公元593年），“天台大师”高僧智顗在湖北玉泉山捐募建玉泉寺。唐德宗贞元十八年（公元802年）的一方碑刻认定就是他做了个梦，关公父子显灵，并为创建玉泉寺出力。后来还有禅宗北派六祖神秀来到玉泉山创建道场，欲毁一祠，又梦见关公“提刀跃马，于云雾之中往来驰骤”，具言前事。神秀遂欣然以关公作为护法伽蓝。从唐代开始，玉泉寺就有关羽祠，这可视作关公信仰的发端。

中国早有“黄帝战蚩尤”的传说，“关羽斩蚩尤”就是依附“黄帝战蚩尤”传说而来。目前最早记述这个故事是被视为《水浒传》祖本，成书于宋元年间的《大宋宣和遗事》元集。大略为北宋崇宁五年夏天，山西解州盐池有蛟作祟，皇帝请来第三十二代天师张继先平息，很快成功。宋徽宗抚劳其功，张天师说是蚩尤作乱，于是请来两位神将出力，其中一位就是关羽。金元以后，全真道和其他道教派系也陆续接受关公神话及其神灵，如全真道曾以关羽为四元帅之一。这大大提高了关公的神权，道教亦借此增加其影响力，也为日后关公被明代封敕为“三界伏魔大帝，神威远镇关圣帝君”，以至近世台湾传出关公为“第十八代玉皇大帝”的说法奠定了基础。

随着佛道两教争相神话关羽，儒家尤其是理学出于“神道设教”的政治设计，也开创出一整套国家体制下的儒家祠庙祭祀制度，并且开始用儒学系统阐释关羽精神。他们以关羽“兴复汉室”作为“《春秋》大一统”理念的标志，以“尊刘贬曹”为“正统史观”的泾渭，以“宁死不屈”作为“忠节相尚”的象征。随着理学在元明清时代上升为国家意识形态，关羽形象也愈加完美了。

从南宋开始，由于《三国志通俗演义》及其续后版本，使三国故事得以广泛流传，而其中最着力歌颂便是关公形象。乾隆时期特命庄亲王、张照等人辑录和整理了供内廷演出的三国联合大戏《鼎峙春秋》共239出，其中关羽戏占了很大比重，情节大部分来自《三国演义》。清代京剧起初剧码中就有155出三国戏，而以关羽为主角的则占五分之一，并逐步形成了以饰演关羽为主的“红生”行当。可以说，戏曲亦推动了关羽的忠义及神勇形象，是关羽崇拜更趋普及的一个重要里程碑。

关羽传说大体上经历了四个阶段：第一个阶段源于佛教中国化。天台宗为在荆楚地区传播佛教，借用关羽显灵，帮助修建玉泉寺，并且愿为佛教护法，成为“伽蓝神”。第二阶段是公元十一世纪北宋时，关羽成为军队护佑之神，传说能够率领阴兵为宋军助阵，帮助他们取得胜利，这也是依托佛教战神毗沙门天王的神话传说转化而成。第三阶段是公元十三世纪，宋元道教“关公战蚩尤”的神话，使他成为道教尊神。第四个阶段则是明清以后，各地民间不断涌现“关公显灵”传说，扶危济困，从中可反映了关羽崇拜之形成与神话传说增多有着十分密切的关系。

关羽历史遗物不断出现，是关羽崇拜形成的重要标记。符、印是道教镇魔的主要工具。关公成为道教主神以后，照例要为他托印。于是宋代以后儒道结合，陆续开始出现关公印绶，主要是按照《三国志》叙述其生前担任的职务铸造。北宋开始有地方治安官员集体为关公立庙，求护一方平安。金、元、明、清历代相沿，衙役业都以此同业大英雄为开宗祖师，世代奉敬。一直延续至今，在香港、澳门以及台湾刑警，都仍留存着警员行业崇拜风习。近年还随华警传播到英国、加拿大警界。