Родился 29 января 1942 г. в провинции Гуантанамо (Куба) в семье рабочего. В младенчестве потерял родителей, его воспитание взял на себя дядя, брат матери. С девятилетнего возраста начал подрабатывать: торговал фруктами, работал чистильщиком обуви. В 13 лет устроился на мебельную фабрику, где сначала был чернорабочим, затем учеником столяра.
В 1961 г. окончил Технологический институт им. Эхерсито Ребельде. Затем был направлен на учебу в СССР, где в 1961-1962 гг. прошел курс в Ейском высшем военном авиационном училище летчиков, освоил истребитель МиГ-15. В 1969-1971 гг. прошел обучение в Высшей школе революционных вооруженных сил им. Антонио Масео Гомеса.
С 1962 г. служил в Военно-воздушных силах (ВВС) Кубы пилотом-инструктором. В октябре 1962 г. во время Карибского кризиса совершил более 20 боевых вылетов на МиГ-15 с целью разведки и перехвата американских самолетов. В 1963 г. его назначили начальником боевой подготовки авиаполка.
В 1971-1975 гг. был начальником штаба истребительной авиабригады, базирующейся в г. Санта-Кларе (провинция Вилья-Клара, Куба). Одновременно с 1972 г. являлся заместителем командира, с 1973 г. - командиром этой авиабригады. В 1976 г. в звании подполковника был назначен заместителем командира крупного авиационного соединения.
Летчик-истребитель I класса (1968), летчик-инструктор (1968). К 1978 г. налетал более 1,4 тыс. часов.
1 марта 1978 г. подполковник ВВС Кубы Арнальдо Тамайо Мендес был выбран одним из кандидатов на советско-кубинский космический полет в рамках программы "Интеркосмос". Прошел подготовку в Центре подготовки космонавтов им. Ю. А. Гагарина. В октябре 1978 г. его назначили в основной экипаж космического корабля "Союз-38".
18-26 сентября 1980 г. совершил свой единственный полет в космос на "Союзе-38" в качестве космонавта-исследователя, командиром интернационального экипажа был Юрий Романенко. Советско-кубинский экипаж работал на орбитальной станции "Салют-6" с находящимися там членами четвертой основной экспедиции Леонидом Поповым и Валерием Рюминым. Во время восьмидневной миссии Тамайо Мендес и Романенко провели около 20 научных экспериментов, в том числе по кубинской программе.
Всего Арнальдо Тамайо Мендес провел в космосе 7 суток 20 часов 43 минуты. Он стал первым кубинцем и латиноамериканцем, совершившим полет в космос.
После полета вернулся на военную службу. В декабре 1980 г. ему присвоили звание полковника, в феврале 1996 г. - бригадного генерала ВВС Кубы.
С начала 1980-х г. по начало 1990-х гг. возглавлял Общество военно-патриотического воспитания молодежи.
С 1990-х гг. занимал должность начальника Управления внешних сношений Министерства революционных вооруженных сил Республики Кубы.
Неоднократно избирался депутатом Национальной ассамблеи народной власти Республики Куба, в последний раз - в 2018 г. По состоянию на апрель 2021 г. был председателем парламентской группы дружбы Кубы и России.
Являлся вице-президентом Общества советско-кубинской дружбы (ныне Российское общество дружбы с Кубой). Возглавляет Ассоциацию дружбы "Куба - Россия".
Герой Республики Куба (1980), Герой Советского Союза (1980).
Награжден орденом "Плайя Хирон" (1980), а также советским орденом Ленина (1980), российскими орденом Дружбы (2011) и медалью "За заслуги в освоении космоса" (2011).