築城年代は定かではない。一般的には1535(天文4)年に宮川安定によって築かれたのを始まりとするが、1500(明応9)年に竹腰尚綱によって築かれた牛屋城が始まりともされる。
　1544(天文13)年、尾張の織田信秀が大垣城を攻め落とし織田信辰を城主とする。しかし、3年後には斎藤道三の軍勢が攻略し竹腰尚光を城主とした。
　1559(永禄2)年、美濃三人衆の一人･氏家直元(卜全)が大垣城主となり、1567(永禄10)年には織田信長の家臣となる。1583(天正11)年には池田恒興が大垣城主となるが、翌年の小牧･長久手の戦いで討死し、家督を継いだ池田輝政も岐阜城へ転封となる。その後も羽柴秀次，羽柴秀長，加藤光泰，一柳直末，羽柴秀勝と目まぐるしく城主交替があり、1590(天正18)年に伊藤盛景(祐盛)が大垣城主となると、このときはじめて天守があげられた。盛景の没後、嫡男の盛正が家督を継ぐが、1600(慶長5)年の関ヶ原の戦いでは石田三成の要請によって城を明け渡し今村城に移った。西軍本隊が関ヶ原に移動すると、城内には福原長堯らが守将として残るが、西軍が敗北すると東軍に攻囲され落城する。そのときの逸話が『おあむ物語』として残っている。
　江戸時代に入り、1613(慶長18)年には石川忠親によって総堀が加えられ、松平忠良が天守を改修した。その後、1649(慶安2)年に戸田氏鉄によって明治に至る姿とされた。
　戸田氏改修後は並郭式に本丸と二ノ丸を並べ、その周囲を三ノ丸で囲い、更に外周は惣構としていた。本丸には北西隅に4重4階(3重4階とも)の複合式層塔型天守を上げ、3重櫓1基に2重櫓を3基、二ノ丸に月見櫓など3重櫓を4基、三ノ丸には2重櫓4基，平櫓1基などが建て並べられ、本丸に2つ，二ノ丸に1つ，三ノ丸に大手門など大小5つ、外郭に南大手門など大小7つの門が開かれていた。
　1873(明治6)年の廃城令により廃城となったが、天守など一部の建物は破却を免れ、1936(昭和11)年に天守等が国宝(旧国宝)に指定されたが、1945(昭和20)年7月の大垣空襲により天守や艮櫓などが焼失してしまった。