楚地自古崇尚巫風，直至隋代，其習猶故。荊州是關羽一生事業的頂點，也是他功敗垂成之地。南北朝時期，江陵城內出現了一位十分靈驗的「城隍神」，這位城隍神便是曾經修築堅固江陵城的關羽。關公信仰的中心地區曾經過四次大範圍轉移：第一次是隋唐時以玉泉寺為中心的荊楚地區；第二次是北宋以解州為中心的山陝河洛地區；第三次是元明清以京師為中心的華北地區；第四次是明代中葉以「抗倭」為標誌的江浙閩廣地區。

隋文帝開皇十三年（公元593年），「天台大師」高僧智顗在湖北玉泉山捐募建玉泉寺。唐德宗貞元十八年（公元802年）的一方碑刻認定就是他做了個夢，關公父子顯靈，並為創建玉泉寺出力。後來還有禪宗北派六祖神秀來到玉泉山創建道場，欲毀一祠，又夢見關公「提刀躍馬，於雲霧之中往來馳驟」，具言前事。神秀遂欣然以關公作為護法伽藍。從唐代開始，玉泉寺就有關羽祠，這可視作關公信仰的發端。

中國早有「黃帝戰蚩尤」的傳說，「關羽斬蚩尤」就是依附「黃帝戰蚩尤」傳說而來。目前最早記述這個故事是被視為《水滸傳》祖本，成書於宋元年間的《大宋宣和遺事》元集。大略為北宋崇寧五年夏天，山西解州鹽池有蛟作祟，皇帝請來第三十二代天師張繼先平息，很快成功。宋徽宗撫勞其功，張天師說是蚩尤作亂，於是請來兩位神將出力，其中一位就是關羽。金元以後，全真道和其他道教派系也陸續接受關公神話及其神靈，如全真道曾以關羽為四元帥之一。這大大提高了關公的神權，道教亦借此增加其影響力，也為日後關公被明代封敕為「三界伏魔大帝，神威遠鎮關聖帝君」，以至近世台灣傳出關公為「第十八代玉皇大帝」的說法奠定了基礎。

隨着佛道兩教爭相神話關羽，儒家尤其是理學出於「神道設教」的政治設計，也開創出一整套國家體制下的儒家祠廟祭祀制度，並且開始用儒學系統闡釋關羽精神。他們以關羽「興復漢室」作為「《春秋》大一統」理念的標誌，以「尊劉貶曹」為「正統史觀」的涇渭，以「寧死不屈」作為「忠節相尚」的象徵。隨着理學在元明清時代上升為國家意識形態，關羽形象也愈加完美了。

從南宋開始，由於《三國志通俗演義》及其續後版本，使三國故事得以廣泛流傳，而其中最着力歌頌便是關公形象。乾隆時期特命莊親王、張照等人輯錄和整理了供內廷演出的三國聯合大戲《鼎峙春秋》共239齣，其中關羽戲佔了很大比重，情節大部分來自《三國演義》。清代京劇起初劇碼中就有155齣三國戲，而以關羽為主角的則佔五分之一，並逐步形成了以飾演關羽為主的「紅生」行當。可以說，戲曲亦推動了關羽的忠義及神勇形象，是關羽崇拜更趨普及的一個重要里程碑。

關羽傳說大體上經歷了四個階段：第一個階段源於佛教中國化。天台宗為在荊楚地區傳播佛教，借用關羽顯靈，幫助修建玉泉寺，並且願為佛教護法，成為「伽藍神」。第二階段是公元十一世紀北宋時，關羽成為軍隊護佑之神，傳說能夠率領陰兵為宋軍助陣，幫助他們取得勝利，這也是依託佛教戰神毗沙門天王的神話傳說轉化而成。第三階段是公元十三世紀，宋元道教「關公戰蚩尤」的神話，使他成為道教尊神。第四個階段則是明清以後，各地民間不斷湧現「關公顯靈」傳說，扶危濟困，從中可反映了關羽崇拜之形成與神話傳說增多有着十分密切的關係。

關羽歷史遺物不斷出現，是關羽崇拜形成的重要標記。符、印是道教鎮魔的主要工具。關公成為道教主神以後，照例要為他托印。於是宋代以後儒道結合，陸續開始出現關公印綬，主要是按照《三國志》敍述其生前擔任的職務鑄造。北宋開始有地方治安官員集體為關公立廟，求護一方平安。金、元、明、清歷代相沿，衙役業都以此同業大英雄為開宗祖師，世代奉敬。一直延續至今，在香港、澳門以及台灣刑警，都仍留存着警員行業崇拜風習。近年還隨華警傳播到英國、加拿大警界。