The discovery of penguins is closely bound up with the development of shipbuilding and the following journeys of exploration. When at the end of the 15th century the first galleon was build, they, for the first time, had a ship that was able to sail on open sea. So Portuguese and Spanish seafarers left to explore far-away countries. While such voyages lasts many years and preserves didn't exist, they were forced to go ashore for supplies of fresh water and food.

In all probability the Portuguese explorer Bartholomeu Diaz was the first European who ever saw a penguin. He firstly reached in 1488 the Cape of Good Hope on the southern point of Africa, but never mentioned a penguin in his notes.
Alvero Vello, who sailed with Vasco Da Gama in 1497 around the Cape of Good Hope, first mentioned penguins in his travel book, although he called them "otilicarios" like the auks in the north.
"They're as big as ducks, but can't fly because they have no feathers on their wings. These birds, of which we slaughtered as many as we could, cried like jackass..." That penguins can't fly is of course right, but he probably didn't take a proper look at the feathers on their wings.

This first contact lead to a four and a half centuries during pursuit and decimation. Luckily he didn't became extinct like the Great Auk before. But unfortunately the explorers left a real threat to the penguins behind : namely rats.

More than 100 years later, in the so called "New World", the first South American penguin is discovered. He is firstly mentioned in 1519 in the diary of Antonio Pigafetta, a fellow traveller of Magelhaen. He too described them as gooses, with the advantage that they not only taste good, but also are easy to catch as they can't run away fast.

Sir Francis Drake too mentioned in 1578 Patagonia (South America) as origin for a rare bird, notably the magellanic penguin.