Jabarkan Real Madrid dari Fernando Gago

Pada 15 November 2006, Presiden Real Madrid mengkonfirmasi penandatanganan Gago serta rekan senegaranya Gonzalo Higuain dari River Plate, sebagai bagian dari kebijakan untuk merekrut pemain muda secara bertahap untuk menggantikan bintang-bintang tua di skuat. Namun, berita keberangkatan Higuain untuk bermain di Madrid adalah prematur karena River Plate menolak tawaran € 10 juta dari El Real, mereka menyatakan akan lebih suka bila Higuain tetap di River Plate sampai setidaknya Juni 2007. Selama jendela transfer Amerika Selatan tahun 2006, nama Gago juga dihubungkan dengan AC Milan. Namun, Ariedo Braida, ahli transfer Milan, seperti dikutip, "Mereka [Gago dan Higuaín] hanya ingin pergi ke Madrid". Transfer itu akhirnya disepakati pada 19 Desember 2006 untuk harga € 20,4 juta. Sejak pindah ke Real Madrid, ia telah tampil sangat impresif di posisi gelandang bertahan, yang menyebabkan perbandingan dengan mantan "nomor 5" Argentina lainnya seperti Fernando Redondo dan Jorge Valdano menurut para pakar.

Gago melakukan debut untuk Madrid dalam kekalahan 2-0 La Liga melawan Deportivo La Coruña pada 7 Januari 2007. Namun, karena kinerja tim yang buruk, Gago tidak mampu untuk menampilkan bakatnya, ia digantikan oleh pemain pengganti Ronaldo. Namun, seminggu kemudian saat melawan Real Zaragoza di Stadion Santiago Bernabéu, kinerja Gago terangkat bersama dengan teman satu timnya. Real Madrid mengalahkan Real Zaragoza 1-0, dengan gol dari Ruud van Nistelrooy.

Pada 20 Mei 2007, saat skor imbang 2-2 melawan Recreativo Huelva, Fernando Gago pada menit terakhir membantu Roberto Carlos untuk mencetak gol di akhir pertandingan. Real berhasil mengalahkan Recreativo 3-2 di Stadion Nuevo Colombino dan pergi untuk memenangkan gelar liga 2006-07.

Sebelum awal musim 2007-08, Gago mengubah nomor punggungnya dari 16 menjadi 8. Musim keduanya di klub, Gago menunjukkan kemampuan sejati dengan serangkaian pertunjukan kelas atas di pusat lini tengah Madrid. Dia berhasil mendapatkan tempat di tim pertama, menyisihkan Mahamadou Diarra dan Gago juga merupakan tokoh kunci klub dalam meraih gelar liga dua kali berturut-turut.

Di awal musim 2008-09, Gago hanya bermain di dua pertandingan karena cedera yang di alaminya. Dia berhasil pulih tepat waktu dan dapat bermain pada pertandingan La Liga 27 Oktober 2008 melawan Athletic Bilbao. Madrid menang 3-2 dan Gago dipuji untuk penampilannya di lini tengah bersama Wesley Sneijder. Juga di musim ini, Gago mencetak gol pertamanya untuk Madrid, sebuah sundulan dari tendangan bebas tidak langsung yang disampaikan oleh Guti saat melawan Sevilla FC untuk menyamakan skor 3-3, tetapi mereka kemudian kalah 3-4 dengan gol dari Renato pada menit ke-82.

Pada akhir musim, Fabio Cannavaro kembali ke Juventus dan meninggalkan nomor punggung 5, Gago yang awalnya ingin nomor itu ketika ia pertama kali masuk Real Madrid akhirnya memakainya. Nomor punggung Gago sebelumnya 8 diberikan untuk Kaká. Di bawah pelatih José Mourinho, Gago berjuang untuk mendapatkan tempat di tim utama karena cedera panjang dan preferensi Mourinho yang lebih memilih Xabi Alonso dan Sami Khedira sebagai gelandang bertahan.