堀越城の名が初めて文献に見えるのは、南北朝時代、建武三年(南延元元年、一三三六)のことである。「南部家文書」の建武四年(一三三七)七月日曽我貞光軍忠状案には、当時足利方として行動していた曽我貞光が、前年七月「新里・堀越両所」に「楯」を築いたところ、南党勢の倉光孫三郎が攻撃を仕掛けてきたが、奮戦の末、撃退したことが記されている。
　曽我貞光は、津軽曽我氏の嫡流で、鎌倉幕府滅亡後、いちはやく朝廷側につき、元弘三年(一三三三)から翌建武元年の北条氏与党反乱の際には、国府＝建武政府側に立って奮戦した。しかし、建武新政府の政策に対する不満から、建武二年(一三三五)十月、足利尊氏が鎌倉で反旗を翻すと、これに応じ、その後は安藤家季とともに一貫して津軽足利勢の中心となって活躍した。建武三年(南延元元年・一三三六)正月以降、貞光・家季らは、南党勢の守る藤崎城・船水楯・小栗山楯・田舎楯を攻撃。これに対して、南部・小笠原・倉光孫三郎らの南党勢も安藤方の楯を襲うなど、激しい合戦が続いた。堀越・新里楯の構築はこうした合戦の中で起こったことである。新里もまた堀越北方の平川沿いの土地であり、ともに貞光が本拠の岩楯・大光寺を守る前線拠点として構えたものであろう。
　津軽における南北両党の合戦はその後も続き、十四世紀後半に津軽曽我氏は南部氏によって滅ぼされるが、「堀越楯」のその後については記録もなく不明である。
　南北朝時代の「堀越楯」の実体については不明だが、一九七六～七七年、国道七号石川バイパス建設に伴う緊急調査が行われた際に、二の丸跡の東部から、東西に走る幅三～六メートル、深さ一～二メートルの薬研堀の跡が、五本見つかった。年代は、室町時代中期のものが二本、戦国時代のものが三本。堀の形も掘られた方向も、後の堀越城のものと全く異なるという(『史跡堀越城跡・石川バイパス遺跡発掘調査報告書』一九七八年)。断定はできないが、このうち最も古い時期の堀が「堀越楯」のものである可能性がある。その場合、堀の発見された場所が平川寄りの東の地区であることから考えて、当初の堀越楯は平川沿いの段丘状の高まりを利用して構築されたものであり、西に堀を掘って曲輪を設け、さらに東西に走る堀で内部をいくつかに区分するという、同じ弘前市内の境関館などと同様の形が想定されてくる。