伝承では天平年間（729-748）に防人の在営地として築かれたと伝えるが、北日本の蝦夷を治めるための前進基地において防人と言ったかどうかは疑問がある。鎌倉期には佐々木氏、執権北条氏の一族が居住したらしい。南北朝期には北朝の拠点となり城郭として整備された。
室町期に上杉氏が越後守護として入国すると、守護代長尾氏がはじめ蔵王堂（新潟県長岡市）に配置され、のちに守護勢力が弱まると長尾氏の一族、古志長尾氏が栖吉城に入り、栃尾城は在地土豪支配のための支城として整備され、城代に本庄実仍が任ぜられた。
永正四年（1507）、顕定の弟で越後守護の上杉房能が春日山城主・守護代長尾為景と対立し敗走中に自刃、関東管領の山内上杉顕定は養子、憲房とともに永正六（1509）年越後に出陣、一時為景勢を越中に敗走させたが、翌永正七（1510）年六月二十日、為景の襲撃で顕定は長森原で自刃した（長森原合戦）。これによって長尾為景は事実上越後国主の実権を掌握したが、天文五（1536）年八月に為景は嫡子・晴景に家督を譲り、天文十二（1543）年十二月に没した。晴景は国人領主たちの叛乱を鎮圧することが出来ず、当時春日山城下の林泉寺にいた弟の虎千代（長尾景虎、のちの上杉謙信）を還俗させ栃尾城に配置した。謙信はこの栃尾城下で、敵対する三条城主・長尾俊景らの攻撃を退けたと言われる（刈谷田川合戦）が、史実であるという確証は無い。この一連の栃尾城付近での叛乱鎮圧戦が当時十四歳の景虎の初陣と言われる。景虎はその後も黒滝城の黒田秀忠の謀反討伐などで武勇を示し、揚北や越後中郡の諸将の支持を得た。これに危機感を抱いた晴景は景虎討伐軍を発したが、景虎は米山合戦で大勝し春日山城下に迫った。この内紛を憂いた守護・上杉定実が両者を調停し、天文十七（1548）年、景虎は晴景の養子となって守護代長尾家を嗣ぐ事となり、栃尾城から春日山城に移った。
謙信の治世下では、本庄実乃は春日山城下に移り、栃尾城には本庄玖介、宇野左馬充が栃尾城代として配備され、「栃尾衆」が編成された。天正三（1575）年には栃尾衆は計240名の軍役を負っている。
天正六（1578）年三月、謙信は春日山城内で急死し、上田長尾氏出身の景勝と、小田原北条氏から養子に入った三郎景虎が家督をめぐって対立した（御館の乱）。この乱では栃尾城主の本庄秀綱は三郎景虎方につき、天正六（1578）年五月には景勝方の直江信綱を攻め、八月には南魚沼に出兵、九月には御館に入城した。十月二十四日の戦闘で景勝軍が勝利すると、秀綱は十一月に栃尾城に帰り、援兵を待った。しかし三郎景虎は天正七年三月に御館を脱出、堀江宗親を頼り鮫ヶ尾城に逃れたが、堀江の寝返りにより三月二十四日、鮫ヶ尾城で自刃した。天正八（1580）年四月、景勝は三郎景勝方の残党討伐のために春日山城を出立し、三条城を平定した後に四月十五日、栃尾城を攻めに向かい、四月二十二日には城下を焼き払った。本庄秀綱は栃尾城を棄て、会津に落ち延びて、栃尾城は陥落した。
栃尾城が陥落後、上杉景勝は上田荘出身者を栃尾に配備、佐藤甚助忠久を城主に任じた。慶長三（1598）年の上杉景勝会津移封により、廃城となった。
