築城年代は定かではないが南北朝時代に築かれたと云われる。 南北朝時代に越後国守護となった上杉憲顕が南朝方の兵を追い、家臣古志長尾氏が在城した。
古志長尾氏は長尾孝景の頃に栖吉城を築いて居城を移し、その後、長尾景為の弟長尾為重が城主となったという。天正6年(1598年)上杉謙信没後に起こった御館の乱では上杉三郎景虎方となり、上杉景勝によって攻められ落城、景勝の家臣松川修衡が城主となった。
慶長3年(1598年)上杉景勝は会津へ転封となり、かわって堀秀治が入封すると弟堀親良が四万石で蔵王堂城主となる。慶長5年(1600年)関ヶ原合戦では東軍に属し、上杉景勝が越後の旧臣を扇動して下田村で一揆を誘発すると、親良は陣頭にたってこれを鎮め、徳川家康・秀忠父子より感状を得ている。しかし、慶長7年(1602年)親良は病気と称して堀秀治の二男鶴千代を養子に迎えて家督を譲り隠居した。
幼少の鶴千代を後見したのが坂戸城主堀直寄で、直寄は坂戸城より蔵王堂城へ移り長岡城の築城をはじめるが、鶴千代が早世してしまう。長岡城の完成を見る前に堀氏が家督相続を巡る争いで改易となり、直寄は徳川家康に出仕して信濃国飯山へ転封となった。
城は信濃川東岸の平地に築かれていた。現在は安禅寺の境内として本丸部分のみが残っている。