元和8年(1622年)内藤清政によって築かれた。
内藤清政は関東総奉行を務めた内藤清成の次男で、元和3年(1617年)兄清次が没した為、その遺領を継ぎ二万六千石の大名となった。元和8年(1622年)に安房国勝山に三万石で転封となり、勝山陣屋を構えて安房勝山藩となった。
元和9年(1623年)清政が没すると嗣子なく改易となったが、内藤家の功績により、寛永3年(1626年)清政の弟政勝が二万石を賜り勝山藩が再興となった。しかし、この政勝も寛永6年(1629年)に没し嫡子も幼かったため一万五千石を幕府に返納、内藤家は旗本五千石として内藤重頼が継いだ。この家系は後に大名として復活し信濃国高遠藩となっている。
内藤家ののちは廃藩となっていたが、寛文8年(1668年)酒井忠国が一万石で安房勝山藩主となる。酒井忠国の父は小浜藩主酒井忠勝の嫡子忠朝であったが、忠朝は父忠勝の勘気を被り廃嫡となり蟄居させられていた。忠朝が没したのち、忠国は小浜藩主酒井忠直から安房と越前で一万石を分知され諸侯に列した。
天和2年(1682年)忠国は安房、上野で五千石を加増され一万五千石となる。翌天和3年(1683年)忠国が没して忠胤が家督を継ぐと、三千石を弟忠成に分知し、一万二千石となる。以後、酒井氏が代々続いて明治に至る。
勝山陣屋は勝山城の北麓に築かれていたが、現在は宅地などになってい遺構はない。