Ранее Мексика и САДР были частью Испанской империи. С 1884 года Испания контролировала территорию Западной Сахары (также известной как Испанская Сахара) и управляла ею до 1975 года. В ноябре 1975 года Испания согласилась разделить часть территории с Марокко и Мавританией после подписания Мадридских соглашений. В том же месяце 350 000 марокканцев и 20 000 марокканских солдат провели «Зелёный марш» на Испанскую Сахару, чтобы заставить Испанию передать спорную территорию. Испанские войска вскоре покинула Западную Сахару. В феврале 1976 года Полисарио (политическое движение народа сахарави) учредил и объявил о создании правительства в изгнании в Алжире и назвал страну «Сахарской Арабской Демократической Республикой» (САДР)[1][2].
В 1975 году представители САДР посетили Мексику, чтобы заручиться поддержкой независимости[3]. В 1978 году министр иностранных дел САДР Башир Мустафа Сайед осуществил визит в Мексику[4]. 8 сентября 1979 года во время VI Конференции народов Движения неприсоединения министр иностранных дел Мексики Хорхе Кастаньеда заявил, что Мексика признала САДР как государство в рамках международного сообщества. 24 октября 1979 года между странами были установлены дипломатические отношения. В 1988 году САДР открыла дипломатическое представительство в Мехико[3]. В 1979 году Мексика назначила своего посла в Алжире Оскара Гонсалеса послом по совместительству с САДР[4].
В марте 2010 года делегация сахарави прибыла в Мексику и провела переговоры с сенаторами, в том числе с Ейдцкол Полевнской (вице-председателем сенатской комиссии Мексики по международным отношениям с Африкой), чтобы обсудить ситуацию в САДР[6][7]. В том же месяце председатель сената Мексики Карлос Наваррете Руис посетил Алжир, где провел переговоры с президентом САДРМухаммедом Абдельазизом и направился в вилайет Тиндуф, чтобы посетить лагеря сахарских беженцев и ознакомиться с их нуждами[8]. В сентябре 2010 года президент САДР Мухаммед Абдельазиз посетил Мексику, чтобы принять участие в праздновании двухсотлетия независимости Мексики[9]. В декабре 2012 года Абдельазиз прибыл в Мексику, чтобы присутствовать на инаугурации президентаЭнрике Пенья Ньето[10].
В марте 2013 года министр иностранных дел САДР Мохамед Салем Салек посетил Мексику и встретился со своим коллегой Хосе Антонио Мид в штаб-квартире министерства иностранных дел Мексики[11]. В 2014 году мексиканская делегация из числа депутатов посетила лагеря сахарских беженцев в вилайете Тиндуф (Алжир)[12]. В январе 2017 года другая мексиканская делегация посетила лагеря сахарских беженцев в вилайете Тиндуф[13].