根據廟內鑄於清雍正八年（即一七三〇年）的古鐘推算，九龍城侯王古廟大概建於一七三〇年或以前，以供奉楊侯大王。該廟於一九二八年由華人廟宇委員會接管。
清廷在一八四七年至一八九九年駐軍九龍寨城期間，寨城的官將多曾於侯王古廟參拜。侯王古廟是本港少數廟宇仍保留了大量與九龍寨城有直接關係的歷史文物，例如由首任九龍巡檢司許文深於一八四七年所捐的香爐。此外，其他著名的文物如一八八八年的「鶴」字石刻，至今仍可見於廟後的巨石上。
侯王古廟建築群座落於石砌高台之上，包括廟宇主建築及其後加建的廂房、亭、刻石等。廟宇前方建有獨立的香亭，其歇山頂以精美的花崗岩石柱和木樑架支撐。神壇設於廟宇的後殿，是敬拜侯王和其他神祇（如觀音）的地方。後殿的山牆採用了「五岳朝天式」設計，在香港甚為罕見。
侯王古廟於二〇一四年列為古蹟。