Patagonlar hakkındaki ilk bilgi, 1520'lerde dünyanın etrafını dolaşan Ferdinand Magellan ve mürettebatının onları Güney Amerika sahillerinde gördüklerini iddia etmeleridir. Magellan'ın uzun yolculuğunun tarihçisi ve yolculuktan sağ çıkan az sayıdaki kişiden biri olan Antonio Pigafetta yerlilerle karşılaşmalarını ve boylarının normal insanın iki katı olduğunu yazmıştır:
"Bir gün aniden çıplak ve dev boyutlarda bir adamı limanın sahilinde gördük, dans ediyordu, şarkı söylüyordu ve kafasına toprak atıyordu. Kaptan-general Magellan, adamlarımızdan birini devin yanına yolladı, o da aynı hareketleri barış işareti olarak yapacaktı. Bunu yaparak, devi kaptan-generalin beklediği adacığa getirdi. Dev, kaptan-generalin ve bizim yanımızda çok şaşırdı ve gökten geldiğimizi düşünerek parmağını havaya kaldırarak işaretler yaptı. O kadar uzundu ki ancak beline geliyorduk ve orantılıydı..."
Pigafetta ayrıca Magellan'ın bu insanlara "Patagão" (veya Patagoni ) adını bağışladığını kaydetmiş fakat bağışlamanın ayrıntılarını açıklamamıştır. Pigafetta'nın zamanında bu ismin kaynağı olarak pata veya ayak olarak düşünüldüğü ve "Patagonia" kelimesinin "Büyük Ayak Toprakları" anlamına geldiği şeklinde yorumlanmıştır. Ancak, bu da kökenbilim açısından tartışmalıdır, -gon sonekinin anlamı da açık değildir. Yine de, "Patagonia" ismi ve yerli halkın dev olduğu fikri, sabit kalmıştır. Yeni Dünya'nın daha sonra yapılan ilk haritalarında bölge regio gigantum ("devlerin bölgesi") olarak adlandırılmıştır.
'in "Voyage au pole sud et dans l'Oceanie…" isimli eserinden bir resim] 1579'da, Francis Drake'in gemi papazı Francis Fletcher, Patagonyalılarla uzun buluşmasını yazmıştır.
1590'larda Anthonie Knivet Patagonya'da 3,5 metre uzunluğunda cesetler gördüğünü iddia etmiştir.
1766'da, tuğamiral John Byron'ın kaptanlığındaki HMS Dolphin'in İngiltere'ye geri dönüşünden sonra, dünyanın etrafını dolaşırken Patagonya'da 9 ayak uzunluğunda bir yerli kabilesi gördükleri söylentisi yayılmıştır. Ancak, seferin kayıtlarının 1773 yılında tekrar düzenlenerek yazıldığı metinde, Patagonyalıların sadece 1,98 metre boylarında olduğu yazılmıştır; belki uzun, fakat kesinlikle dev değil.
Byron'ın karşılaştığı insanlar büyük ihtimalle bölgenin yerlileri Tehuelçelerdir. Daha sonraki dönemlerin yazarları, Patagonya devlerinin bir aldatmaca veya en azından abartma ve bölge hakkında ilk bilgi veren Avrupalıların notlarının yanlış yorumlanması olduğunu düşünmüşlerdir.
