The bone from the Great Auk, a species last seen in British waters on St Kilda in 1840, was recovered at the Kirk Ness site, now known as North Berwick.
It was unearthed during a dig at the Scottish Seabird Centre.
Archaeologists said the find sheds new lights on human habitation of the area in the Middle Ages.
The archaeological dig, by Edinburgh-based Addyman Archaeology, and supported by Historic Scotland, revealed bones of butchered seals, fish and seabirds, including the bone of the Great Auk.
The upper arm bone of the flightless bird was unearthed at the entrance area of an early building and has been radio carbon dated to the 5th to 7th Centuries.
The seabird was a favoured food source in medieval times as it was easy to catch.
Human predation led to the decline of the species, ensuring that by the middle of the 19th Century it had become persecuted and exploited into extinction.
The penguin-like bird was 1m tall and its range at one time extended from the north-eastern United States across the Atlantic to the British Isles, France and Northern Spain.
Tom Brock, chief executive of the Scottish Seabird Centre, said: "The discovery of the Great Auk bone on site at the Scottish Seabird Centre is fascinating but also very sad.
"We are so fortunate in Scotland to have a rich variety of seabirds and we must use the extinction of the Great Auk as a warning to future generations to look after our wonderful wildlife and the marine environment as an absolute priority.
"There are both behavioural and environmental lessons that must be taken from this internationally-important finding, and as an educational and conservation charity we will remain dedicated to inspiring people to enjoy, protect and learn about wildlife and the natural environment."
Tom Addyman, of Addyman Archaeology, said: "The discovery of the Great Auk bone at Kirk Ness is an illuminating find, as we seek to understand and document the importance of the area in the history of wildlife and human habitation in the Middle Ages.
"We hope that its discovery helps historians and conservation experts, such as the Scottish Seabird Centre, to educate future generations about the precious nature of our natural resources."
Rod McCullagh, senior archaeology manager at Historic Scotland, said: "In the last two decades, there has been a renaissance in our understanding of the archaeology and history of early Medieval Scotland.
"The discovery of the remains of domestic buildings and the associated detritus of daily life at Kirk Ness gives us a glimpse of what ordinary life was like in East Lothian at this time.
"That 'daily life' involved the killing of such valuable birds as the Great Auk is no surprise but the discovery of this single bone perhaps attests to a time when hunting did not overwhelm such a vulnerable species."
BBC News. 2014. “'Scotland's dodo' bone found at Scottish Seabird Centre dig”. BBC News. Posted: May 12, 2014. Available online: http://www.bbc.com/news/uk-scotland-edinburgh-east-fife-27372931