1584(天正12)年に近江国日野城の蒲生氏郷が伊勢国12万3千石を与えられ松ヶ島城に入城したが、松ヶ島は伊勢湾に面し城下町の発展性がないと考え、1588(天正16)年に現在の城地である飯高郡矢川庄の四五百森に新たに築城を開始した。松坂城の築城前より、伊勢国司で北畠家の武将･潮田長助が四五百森城を当地に築城していたとされる。築城は急ピッチで行われ、年内に完成したという。城の縄張りは梯郭式平山城で東に大手、南に搦手を配し、外郭に深田堀及び水堀を巡らせた。四五百森北峰の本丸には連結式3重5階の天守が築かれ、その南側に二の丸が置かれた。城下町建設にあたり松ヶ島住人を強制的に移住させ、旧領の近江商人を町の中心部に呼び寄せて日野町とし楽市楽座を設けた。
　氏郷は1590(天正18)年には小田原征伐の軍功により陸奥国会津60万石の大封を得て若松城に移った。代わって入城した服部一忠は豊臣秀次事件に連座したとして自害。次いで古田重勝が入城し、後を弟･重治が襲封したが、1619(元和5)年に石見国浜田城に転封となり、南伊勢は紀州藩の藩領となって城代が置かれた。
　城内の天守以下の櫓や門等の建物は放置され、1644(正保元)年に天守が台風のため倒壊したとされ、以後は天守台のみが残ることとなった。1794(寛政6)年には二の丸に紀州藩陣屋が建てられた。以後、紀州藩領として明治維新を迎え、1871(明治4)年の廃藩置県により廃城となった。
　1877(明治10)年の失火により二の丸御殿を焼亡し、1881(明治14)年までに他の建造物も破却によって失われ、城地には石垣のみが残っている。石垣作りには穴太衆が発案した切込みはぎ,算木積みの工法が使われている。また、殿町御城番屋敷に米倉が現存している。