延文2年・正平12年(1357年)斯波兼頼によって築かれたと云われる。 兼頼は奥州探題斯波家兼の二男で北朝方として出羽国の南朝方である大江氏などを攻略するために山形へ入部した。この時築いたのが山形城の前身という。

斯波氏は後に最上氏を称し、最上氏11代最上義光は天正12年(1822年)谷地城主白鳥氏、寒河江城主寒河江氏、天童城主天童氏を降して領地を拡大する。翌天正13年(1823年)には庄内地方へも侵攻して一旦は領地化したものの、上杉氏の家臣本庄繁長に敗れて庄内を失った。

慶長5年(1600年)関ヶ原合戦では上杉氏討伐の為に北上中の徳川家康と同調して、奥州の諸大名を従え米沢へ侵攻する手筈であったが、上方で石田三成が挙兵した為に徳川家康は上杉討伐を中止し上洛する。上杉景勝は直江兼続を主将として山形へ侵攻させ畑谷城などを落として長谷堂城へ攻め寄せたが、これを抜くことができず、関ヶ原合戦で東軍が勝利した報を受け引き上げた。

関ヶ原合戦後、最上義光は五十七万石の大大名となり、山形城を近世城郭へと大改修する。しかし、元和8年(1622年)最上義俊の時にお家騒動となって改易。近江国大森一万石にに再封されたが、義俊が没すると最上義智が家督を継いだものの幼少相続を理由に五千石に減封、交代寄合の旗本となった。