築城年代は定かではないが南北朝時代に安芸吉川氏によって築かれたと云われる。
この辺りは南朝方の福屋氏が高城を築いて勢力下に治めていたが、北朝方であった安芸吉川氏が高城を攻め落とし、重臣堀氏を配して堀城(桜尾城)を築かせたという。
天文年間(1532年〜1555年)に毛利元就の次男元春が吉川氏の養子となって家督を継ぐことになったが、堀重利はこれを嫌って吉川氏を離れて福屋氏に属した。
永禄4年(1561年)毛利氏に従っていた福屋氏が毛利氏を離反すると、堀重利は三坂で吉川軍を迎え撃ったが敗れ、城内で討死したという。
桜尾城は市木小学校の南西、瑞穂icの北にあり、北へ伸びた丘陵の先端頂部に築かれている。
主郭は山頂で南北に伸びた尾根に段曲輪を配し、最高所に東屋が建てられている。南西に一段下がったところは南尾根を遮断する大堀切に面して土塁があり、南端に石組井戸、北端は大きな竪堀となる。 南尾根を遮断する大堀切は長く、南は「馬ズリ」と呼ばれる二条の竪堀に分かれて伸びている。
主郭の南端から東へ伸びた尾根に出丸がある。西の尾根側に小さな土塁状の高まりがあり、南に谷に向かって竪堀状の溝が続いている。
市木小学校の辺りに桜尾城への道標が出ており、主郭まで遊歩道が続いている。