築城年代は定かではないが、尾呂志氏によって築かれたと云われる。 尾呂志氏は鎌倉時代頃にこのあたりに入部してきたと考えられ、はじめ尾呂志古土井城を築いたが、その後に尾呂志城を築いて移ったと考えられている。
永禄年間(1558年～1570年)には尾呂志孫三郎がいて、その子伝兵衛は堀内氏と婚姻関係にあった。天正年間(1573年～1592年)には尾呂志山城守義利、文禄年間(1592年～1596年)には尾呂志伝兵衛が堀内氏とともに熊野水軍を率いて朝鮮に渡海した。
慶長5年(1600年)関が原合戦で堀内氏が滅亡すると、柳川城主となった田中吉政に仕える。しかし、田中氏も嗣子なく没して改易となり、紀州に戻った伝兵衛は後に藤堂氏に仕えたという。
尾呂志城の明確な遺構はないが、尾呂志小中学校北側の駐車場フェンスのところに案内板が設置されている。近くには的場石とされる石や井戸がある。
明治期に作成したという図面では東西約47m、南北約53mの規模で北西を除いて堀が巡っていたという。