在中國內地，到底有多少關廟？現在還沒有見到精確的統計數字。但就筆者所知，關廟不僅遍布漢族居住地區，而且在邊遠的少數民族居住地區也建有關廟。
最早的關廟建造在何處？有兩種傳說。
一種傳說是，關羽死後，蜀漢皇帝劉備為了給他報仇，便親率大軍東征孫權，他在進軍途中，曾經親自到當陽關羽的亡命之地拜祭，並在當陽玉泉山為關羽建造了武烈廟。現在，這個武烈廟已經不存在。
另一種傳說是，劉備在白帝城亡故後，諸葛亮輔佐阿鬥作蜀漢皇帝，他曾南征孟獲，在此期間，他於夷族之鄉，即現今的雲南省，建造了關廟。當代人李純君先生有一篇文章談到了這個傳說；並且說，至抗日戰爭時期，關廟依然矗立在當地。
李純君有《孔明建關廟於孟獲鄉》一文，刊於中華民國五十年（1961年）《龍岡秋季刊》二九頁。略謂：據傳孔明於三擒孟獲時，使趙雲、魏延與孟氏族人最有力之孟龍、孟虎較重武器；為趙、魏勝之。孔明反置酒為之壓驚，並令其導往黑泉，知有毒，令封閉之；而在黑泉上麵建關侯廟。廟塑關公父子及周倉三泥像，並定以永昌縣（在雲南）縣宰為主祭官，撥大量公田為廟產。並將關侯一生大事，勒石為碑以示邊民，該廟自漢至今猶嶄然矗立於原地，廟貌莊嚴如故；蓋曆代帝王均有重修也。戰時，我遠征軍赴緬甸配合盟軍作戰，道出保山縣（在雲南省。漢時的永昌舊址即在保山縣），經過金錕村及諸葛營各地，得瞻此一間最古老之關侯廟。當年，諸葛亮在“三擒孟獲”（《三國演義》寫為“七擒孟獲”）的少數民族地區建立關侯廟，大概是想以關大將軍的神威震懾“蠻主”，並以他的忠義精神教化夷族，以達到使這些少數民族永遠臣服於蜀漢的目的，符合諸葛亮在《隆中對》中提出的“南撫夷越”的戰略思想。
諸葛亮在少數民族地區建立關廟正史沒有記載。但是，從上述文章的介紹來看，極可能是事實。因為，關羽生前沒有到過那個地方，隻有諸葛亮帶兵去征戰過。那裏也有諸葛亮祠，可能是少數民族或後人建築以垂念他。在諸葛亮征討孟獲後，要挑一個蜀國大將“震懾”夷族，關羽是最理想的人選。當時他已過世，比其他大將名望都高；為他建祠是可能的。而且，當地有關廟是事實。明代著名旅行家徐霞客（1586年-1641年）曾到雲南永昌一帶遊曆過，在他寫的《滇遊日記》中曾多處提到關廟。
梁之南，居廬亦盛，有關帝廟東南向，是為大屯。瑤複上西崖，其南一峰高聳，憑空揖瀑，是為龍光台，上建關帝殿。回盼久之，複下西崖。而且，徐霞客還多次提到諸葛亮。
其西寶蓋山穹立甚高，東下而度一脊，其南北甚狹，度而東，鋪為平頂，即太保山之頂也。……舊武侯祠在諸葛營，今移於此頂。瑐瑦五裏，過神濟橋。其南居廬連亙，是為諸葛營，諸葛之祠在焉。瑐瑧這一方麵足以說明，在明代或明代以前，那裏的關廟就已經有了，而且不止一處；說它始建於諸葛亮時，也有可能。另一方麵也說明，在抗日戰爭時期，我國遠征軍途經這裏出國時曾看到過關廟和諸葛營遺址，不是虛妄之說。如果劉備在世時在玉泉山為關羽建武烈廟，或者諸葛亮在世時於此“夷鄉”建立關廟之說能夠成立，那麼，這兩地的關廟就是我國最早的關廟建築了，比隋代在湖北當陽玉泉山建築的關廟要早三個多世紀。
還有一個傳說，關羽在生前鎮守荊州時，由於聲名卓著，受到當地人士的敬重，因此，曾為他建立了生祠，並塑了像。1932年在廣州一家報紙上曾刊載過一張關羽塑像照片，據照片提供人說：照片中的塑像，就是荊州關羽生祠中的塑像。但是，由於沒有其他任何記載和實物（遺址）佐證——筆者1993年在荊州實進考察時也就關羽生祠的題進行過一些調查，也不得要領——這一說法的可靠性是值得懷疑的。