築城年代は定かではないが南北朝時代に芳賀氏によって築かれたと云われる。 芳賀禅可は宇都宮氏綱の後見として北朝方として戦い、宇都宮氏綱は上野国・越後国の守護職を得た。禅可の子高貞と高家は越後国守護代として越後に入部したが、貞治元年(1362年)に上杉房顕が関東管領となると、足利基氏は宇都宮氏綱から越後守護職を奪って上杉房顕に与える。これによって芳賀高貞・高家兄弟は上杉房顕と戦ったが敗れた。
天文12年(1543年)後に上杉謙信となる長尾景虎が中越地方の国人を統制するために、城主本庄実乃に迎えられた。中越を平定した景虎は天文19年(1550年)兄の晴景に代わって春日山城へ迎えられ長尾家の家督を相続した。
天正6年(1578年)上杉謙信没後に起こった御館の乱では、栃尾城主本庄秀綱は上杉三郎景虎方となり、上杉景勝に攻められ落城した。
慶長3年(1598年)上杉景勝が会津へ転封となると代わって入封した堀秀治の家臣神子田政友が一万石で城主となったが、慶長15年(1610年)堀氏が改易となると廃城となったという。
城は標高227.6mの鶴城山に築かれおり、刈田川が南から東側を流れて天然の堀となっている。
山上は尾根に沿って東西を縦としたｌ字状に曲輪が配置されている。 曲輪は標柱で確認した名前では、北から五島丸・三の丸・松の丸・本丸・二の丸ここから西へ中の丸・びわ丸・狼煙台詰曲輪となっている。各曲輪は概ね堀切によって区切られ、一部の堀切は竪堀となっている。
東麓の栃尾大町にある諏訪神社から登山道がある。車だとそこから県道138号線沿いに北上し道なりに進んで行くと左側に栃尾城への道標があり、林道を通っていけば中の丸下まで行くことができる。