7世紀に成立した。
紀伊国は歴史が古く、 『古事記』には神武天皇が大和に入る時に紀伊熊野を通ったとされるなど、 事実はともかく、 奈良盆地を地盤とするヤマト王権から知られた国であった。 王権は、海人集団を部民に編成する海部の設定を進めた。 また、忌部の設定は「紀氏集団」の在地の祭祀権を揺るがした。 しかし、部民の設定は充分に展開しなかった。 王権はつぎに国造制の導入と屯倉の設定という方策をとった。
天皇や皇后の紀伊行幸で史料に現れた確実な例は、 斉明天皇の西暦658年（斉明天皇4年）紀温湯（牟呂温湯）行幸である。 この11月に有馬皇子の事件が起きた。
奈良時代の官衙遺跡の確実な例として、 御坊市の堅田遺跡が挙げられる。 この遺跡では、周りに柵か塀をめぐらしており、 その内区には庇のついた掘立柱建物を中心に建物が全体として「コ」の字状に建てられており、 外区には倉庫群が二組建てられていたようである。 この堅田遺跡は8世紀前半から後半にかけての遺跡で、 付近に「西郡」の名の字が残っているところから考えて、 日高郡衙跡に比定されている。
平安時代後期に熊野三山（熊野本宮、熊野新宮、熊野那智の連合体）が成立し、 太上天皇（上皇）による熊野御幸がおこなわれるようになると、 熊野古道が整備され熊野詣が流行った。 その他、紀州の三井寺とされた紀三井寺、空海の高野山金剛峯寺、 道成寺、根来寺など大寺大社が紀州の地に建てられた。
平安時代末期には、 特に有田郡の湯浅地方を中心に湯浅党の武士団、 口熊野の田辺・奥熊野の新宮付近に熊野別当家を総帥とする熊野水軍が発達し勢力を伸ばした。 この湯浅党の武士団は平氏方、 熊野水軍は源氏方として源平合戦（治承・寿永の乱）にも関与した。
南北朝時代は湯浅党を中心に南朝勢力が強い国の一つだった。 南北朝合一後は畠山氏が守護であったが、 寺社勢力が強力なために、その支配力は限定的なものにとどまった。
戦国時代には、 ルイス・フロイスが「紀州の地には四つ五つの共和国的な存在があり、いかなる権力者もそれを滅ぼすことができなかった」と述べている通り、 雑賀衆に代表される国人衆や寺社勢力が割拠する状態が続いた。 紀伊の割拠状態は西暦1585年（天正13年）の羽柴秀吉による紀州征伐によって終焉した。 紀伊の最有力勢力である雑賀衆と根来寺は、 小牧・長久手の戦いの際、 秀吉の留守に乗じ岸和田城や大坂に侵攻していたが撃退され、 秀吉の信雄・家康らとの和睦後、 雑賀攻めを招いた。 秀吉方は3月20日に出兵し、 和泉の諸城を落として紀州に攻め入り、 23日に根来寺を焼き討ちした。 紀州の国人や各地の戦闘で敗れた残党なども加わって小さな太田城で抵抗したが、 秀吉は水攻めで約一ヶ月後に降伏させた。 平定後は刀狩りを命じ、跡を秀長に任せ、和歌山城を築造した。
現在の奈良県上北山村と下北山村は、 元は牟婁郡の一部であったが、後に大和国吉野郡に編入された。
現在の三重県の尾鷲市、紀北町、大紀町南部の錦地区は、 元は志摩国英虞郡の一部であったが、西暦1582年（天正10年）に新宮城主の堀内氏善により紀伊国牟婁郡に編入された。
関ヶ原の戦いの後は浅野幸長が入封した（紀州藩）。 西暦1619年に浅野氏が安芸広島へ転封されると、 徳川家康の十男徳川頼宣が和歌山に入封し、 幕末まで紀州徳川家が統治した。