6世紀初頭、フランク王国との戦いに敗れ、国家の重心をイベリア半島へ移した西ゴート王国は、約1世紀をかけて半島全土を支配下におさめた。589年にキリスト教アリウス派からカトリックに改宗していた西ゴートは、イベリアのカトリック化を推進した。

一方、661年に建国されたイスラーム国家のウマイヤ朝は、積極的な拡張政策によって急速に勢力を拡大していた。8世紀初頭までに北アフリカの西端まで版図を広げていたウマイヤ朝は、710年、ジブラルタル海峡を越えてイベリア半島に上陸した。この時は一部の都市を襲撃しただけだったが、西ゴート側の抵抗が弱いのを知り、本格的な遠征軍を組織しはじめた。

翌711年、ターリク・イブン・ズィヤード率いる遠征軍がジブラルタル海峡を越えた。同年7月19日、ターリクはグアダレーテ河畔の戦いで西ゴート軍に壊滅的打撃を与え、国王のロドリーゴを戦死させた。王が死んだ西ゴートには後継者がおらず、その混乱に乗じてウマイヤ朝は支配領域を拡大していった。710年代の終わりまでに、ムスリム勢力はイベリア半島を北上し、カンタブリア山脈以北およびピレネー山脈以北までキリスト教勢力を追い詰めていった。この頃、イベリア半島南部はイスラムのアル・アンダルス（ヴァンダル人の地の意、アンダルシアの語源）と名前を変えた。

征服した土地では新たな統治が始まっていた。ウマイヤ朝はイベリア半島のキリスト教化を推進した西ゴート王国に比べて、宗教に寛容だった。ムスリムは被征服者に対して改宗を強制しなかったが、その代わりにジズヤ（人頭税）を要求した。ユダヤ教徒、キリスト教徒の区別なく、ジズヤを納めれば信仰を保持できた。ただし、ある種の社会的格差は存在しており、そのためにイスラム教に改宗するものが相次いだ。また、高額のジズヤが納められずに北部へ逃亡する者や、反乱に加わる者も少なくなかった。
アストゥリアスの反乱と後ウマイヤ朝の建国アストゥリアスのペラヨ

718年、西ゴート王国の貴族を称するペラヨが、アストゥリアス地方でキリスト教徒を率いて蜂起し、アストゥリアス王国を建国した。多くの史家はレコンキスタの開始をこの年に設定している。722年（あるいは718年、724年とも）、ペラヨはコバドンガの戦いに勝利し、イスラム勢力に対するキリスト教国家として初めての勝利を手にした。これは実際には小規模な戦いに過ぎなかったが、イベリア半島のキリスト教徒にとっては象徴的な初勝利であった。以降、アストゥリアスはレコンキスタの拠点となった。同じ頃、カンタブリアでも豪族のペドロ公がイスラム勢力を排除していた。両国は連携し、ペドロ公の息子のアルフォンソ1世は、ペラヨの娘と結婚した。間もなく両国は統合され、地盤を得たアストゥリアス王国は、徐々に南方への反攻を開始した。

732年、トゥール・ポワティエ間の戦いでフランク王国の宮宰カール・マルテルが勝利を収め、ムスリム勢力のピレネー以北への進出を阻止した。その後の751年にメロヴィング朝からカロリング朝へ代替わりすると、フランクは拡張政策に転換し、イベリア進出を狙い始めた。

一方、ウマイヤ朝は分裂の兆しを見せていた。広大な版図の各地で反乱が頻発していたが、ダマスカスのカリフは何ら有効な手立てを打てなかった。750年、サッファーフがウマイヤ朝を滅ぼし、新たにアッバース朝を興した（アッバース革命）。ウマイヤ朝の王族アブド・アッラフマーン1世はイベリア半島へ逃亡し、756年、コルドバで後ウマイヤ朝を建国した。ただし、アッバース朝のカリフに対する配慮から「コルドバのアミール」を称した。
フランクの侵攻とイベリア北部の独立

後ウマイヤ朝の前途は多難だった。北方のキリスト教勢力、国内のアッバース朝支持者、さらに王位を狙う王族や貴族（ウマイヤ朝の遺臣）が、統治を不安定なものにしていた。このため、アブド・アッラフマーン1世は反抗的勢力を徹底的に弾圧した。しかし、この弾圧のために一部の反抗勢力がフランク王国に接近し、彼らのイベリアへの介入を招くこととなった。

778年、カール大帝率いるフランク軍は南下してサラゴサを包囲したが、本国での反乱の知らせに撤退を余儀なくされた。この時、追撃してきたバスク人との間にロンスヴォーの戦いが起こり、後にこの戦いで戦死したブルターニュ公ローラン（ルオドランドゥス）をモデルに「ローランの歌」が作られた。アブド・アッラフマーン1世は、この機会にパンプローナを攻略し、北部制圧の足がかりを作った。

785年からフランク王国は再度の攻勢に出た。ルートヴィヒ（ルイ）1世に率いられたフランク軍は地中海側から侵攻し、ジローナを攻略してスペイン攻略の橋頭堡とした。フランク軍はその後も南下を続け、801年にはバルセロナを攻略した。後ウマイヤ軍の迎撃によって間もなく侵攻は停止したが、獲得したバルセロナはその後のフランク軍の軍事拠点となった。865年、フランクはバルセロナ伯を置いて、カタルーニャを統治させた。しかし、カタルーニャはしだいにフランクと距離を置き始め、やがては完全な独立勢力となった。

一度は征服されたパンプローナだったが、地元の有力者イニゴ・アリスタが中心となり、まもなく反旗を翻した。イニゴ・アリスタは後ウマイヤ朝の鎮圧軍を撃退し、さらに手を伸ばしてきたフランク軍も撃退した。同じ頃、ハカでもアスナール・ガリンド1世がフランクの貴族を追い出していた。この2つの反乱によって、後ウマイヤ朝、フランク王国ともにこの地方に対する影響力は低下した。805年、アスナール・ガリンド1世がアラゴン伯領を興し、次いで824年、イニゴ・アリスタがナバーラ王国（パンプローナ王国）を興した。隣接する両国は当初から親密な関係を維持し、後の905年、サンチョ1世の代に婚姻を通じて統合した。
レオン王国の建国とアブド・アッラフマーン3世の治世

たび重なるキリスト教勢力の侵攻もあり、9世紀半ばから、後ウマイヤ朝の支配体制は揺らぎ始めた。各地の総督や貴族が独立を画策し、キリスト教徒の反乱と相まって、鎮圧に精力を傾けなければならなかった。最も大規模な反乱はトレドで起こったもので、鎮圧するのに20年以上もかかった。

アストゥリアス王国は、この混乱に付け込んで徐々に版図を広げていき、10世紀初頭までにドゥエロ川以北を支配下におさめた。914年、ガルシア1世の代にレオンへ遷都し、レオン王国（レオン・アストゥリアス王国）へ改名した。

912年、アブド・アッラフマーン3世が即位すると、後ウマイヤ朝の統治能力は回復し始めた。アブド・アッラフマーン3世は、反抗的勢力やキリスト教勢力を抑えて国内の安定を図り、同時に内政にも力を注いだ。彼の統治下でアル・アンダルスの経済は飛躍的に発展した。後ウマイヤ朝の最盛期はこの時期とされている。

この頃、北アフリカでファーティマ朝が興り、その指導者はカリフを自称していた。これに対抗するように、アブド・アッラフマーン3世はそれまでのアミールから、「コルドバのカリフ」を称するようになった。アブド・アッラフマーン3世は、ジブラルタル海峡を越えてモロッコへ兵を派遣し、ファーティマ朝との戦いを開始した。932年、アブド・アッラフマーン3世は、キリスト教勢力を打倒するため、自ら軍を率いて北上した。