盡管麥哲倫不得誌於國王，他還是於1516年向葡王提出了遠航請求。麥哲倫向國王闡釋：“東方的群島必定在離美洲西海岸不遠的大南海中。摩鹿加群島離印度和錫蘭非常遙遠，這樣它們就不可能離美洲很遠。”但當時葡萄牙朝野和曼努埃爾國王滿足於沿亨利王子、迪亞士、達·伽馬等開辟的新航路擴大地盤，掠奪財富。盡管繞道非洲的航路也很遠，曆時久，花費也不少，但總比向汪洋大海做毫無保障的探索要穩當得多。況且麥哲倫計劃的直接目的是控製對香料群島的貿易，而葡萄牙當時已能從印度直接弄到廉價的優質香料。加之在哥倫布航渡美洲後，葡西兩國為了避免爭奪殖民地的摩擦，已在1494年確定了劃分勢力範圍的界限，這對葡萄牙國王也起了點約束作用。因為西行勢必要侵入西班牙的勢力範圍。基於以上諸多原因，曼努埃爾拒絕了麥哲倫的請求。於是，麥哲倫隻得出國去尋求西班牙國王的支持。這樣，就像當年哥倫布向若奧二世國王提出西航請求遭到拒絕，若奧後來又後悔不迭一樣，環球航行、發現地球的偉績和榮譽再次與葡萄牙失之交臂。
1517年10月，麥哲倫離開葡萄牙來到西班牙的塞維利亞，不久法利羅也來到這裏。麥哲倫在塞維利亞受到葡籍西班牙高級軍官巴爾波查的接待，通過巴爾波查又與商會會長、西班牙印度院（Indian House）重要官員阿蘭達結識。1518年麥哲倫還娶了巴爾波查的女兒貝亞特利茲。
麥哲倫和法利羅得到阿蘭達的推薦，於1518年3月在西班牙北部的巴利亞多裏德得以謁見西班牙新王查理一世。查理出生於神聖羅馬帝國哈布斯堡家族，時年18歲。1519年他當選為神聖羅馬帝國皇帝，領有西班牙、德國、南意大利、尼德蘭和西屬美洲殖民地，號稱查理五世。查理是個權勢極大，實力雄厚，熱衷於歐洲和世界霸權的帝王。麥哲倫、法利羅向國王呈獻了一個繪製詳細的彩色地球儀，上麵標出了他所擬定的航線。當時的著名史學家拉斯·卡薩斯在《西印度通史》一書中記述說：“麥哲倫有一個畫得很好的地球儀，上麵畫著整個世界，標出了他所建議的航線。他有意把海峽的位置留下空白，以免有人可能在他之前通過。我問他計劃走什麼路線，他說他要取道聖瑪麗角，這就是我們所說的拉普拉塔河口；然後，再從那裏沿海岸航行，直達海峽”。他還向國王保證，可以不侵犯葡萄牙的勢力範圍，向西走而達到盛產香料的東方島嶼，而香料群島也在教皇劃歸的西班牙勢力範圍內。這時，為了爭取支持，麥哲倫便改口說香料群島屬西班牙了。麥哲倫、法利羅的計劃立即得到查理一世的讚同，大主教方薩加也在旁邊盡力支持。但實際上，摩鹿加一香料群島的中心位置在東經128度上，而教皇子午線的位置一般認為在西經46度上。它對應的東半球經度便是東經134度。因此香料群島應“屬於”葡萄牙。但當時確定經度很困難，也還沒從實踐上證實地球到底有多大。所以香料群島的“歸屬”是個待議待考察的問題。當然後來的實踐證明，西行繞過美洲比東行繞過非洲去香料群島更遙遠。
按照當時的慣例，3月22日，查理一世與麥哲倫、法利羅簽署了遠航探險協定。這麼快便達成了協定，說明了當時西、葡、其他西歐國家之間競爭的態勢，形勢逼人。協定責成麥哲倫、法利羅“在屬於朕的海洋裏發現豐富的香料以及朕最需要的而且能使我國獲利的其他東西”，“擴大我們卡斯提王室的版圖”。協定承諾“在此後10年內，不頒發特許狀給任何想沿你們所選定的路線和方向去探險的人”。並約定“不得在葡萄牙國王陛下的分界線和境界內進行探險”。協定規定，為補償探險者的勞績和所冒的危險，把新發現地區的全部收入（包括利潤和捐稅等）的1/20分給他倆；委任麥哲倫、法利羅為新發現地區的總督，並可世襲。每年賜給他們價值1000杜卡特的商品，用皇家船隻運到新發現地區。協定還規定，如果發現的島嶼超過了6個，麥哲倫、法利羅便可把其中兩個作為自己的領地，獲得領地上全部收入的1/15.首航帶回的貨物，他們可留下1/5.按照協定，查理五世負責為探險提供載重60噸至130噸的船隻共5艘和200多船員。並派人隨船出海監航，去回時均要清賬。