天正十三年(1585)、紀州は羽柴秀吉によって平定された。この時、奥熊野地方に勢力を張っていたのは新宮を本拠とする堀内氏であった。その範囲は現在の新宮市から紀北町にかけての地域で三重県南部と和歌山県南東部といったところであろうか。紀州攻め時、当主の堀内氏善は秀吉に臣従したことにより戦火に見舞われることなく本領は安堵され、和泉、大和、紀伊の領主となった羽柴秀長の配下となった。
　秀吉体制下に置かれたことで、この熊野地方も近世化への変革が求められることになる。その象徴的なものが検地であった。変革には反発が伴うのも常である。
　天正十四年(1586)、北山地域(熊野山間部)に一揆が起きた。秀長は自ら出陣して討伐にあたったが、九州攻めのために中途半端なものに終わったと言われる。
　天正十六年(1588)、多尾城(熊野市五郷町寺谷)に拠る一揆勢を秀長の代官吉川平介(又は平蔵)と堀内氏善が攻めてこれを討伐した。
　熊野は良質の木材産出地として知られ、吉川平介は山奉行の立場を利用して二万本の木材を大坂へ送り、その代金を着服するなどして私腹を肥やしていたことが発覚した。秀吉は激怒して吉川平介を捕縛、処刑して洛中にその首を晒した。
　吉川平介失脚の後、天正十七年(1589)に秀長麾下の藤堂佐渡守高虎、羽田長門守が北山代官として一揆討伐を再開した。この時にこの赤木城が築城されたと言われる。今では後に多くの築城を手掛けることになる藤堂高虎の初期の築城作品として喧伝されている。小規模ながら複雑な虎口形態と石垣の多用という近世城郭の手法が随所に見られる貴重な城でもある。
　藤堂らによる一揆討伐は峻烈を極め、赤木城南西の田平子峠では捕えられた一揆方の人々が処刑梟首された。この時、高虎は周辺の村々に赤木城の完成を祝いに登城せよと触れを出し、祝儀に登城してきた地侍や村人たちを一挙に捕縛して田平子峠で打首に処したという話が伝わっている。この地方の里謡にも「行ったら戻らぬ赤木の城へ、身捨てどころは田平子じゃ」と歌い伝えられている。