"The altitude record is held by a Rüppell's griffon
Gyps rueppelli, a vulture with a 10-foot wingspan. On November 29, 1975 one was sucked into a jet engine 37,900 feet above the Ivory Coast in West Africa. The plane was damaged but landed safely. What the bird was doing up so high I have no idea, since this species is not migratory.
The bird that flies highest most regularly is the bar-headed goose
Anser indicus, which travels directly over the Himalayas en route between its nesting grounds in Tibet and winter quarters in India. They are sometimes seen flying well above the peak of Mt. Everest at 29,035 ft. Birds have some natural advantages for getting oxygen at high altitudes, in particular an arrangement of air sacs that allows them to circulate inhaled air twice through the lungs with each breath--much more efficient than the in-and-out system used by mammals. Bar-headed geese have special adaptations that make them even better at high-flying than other birds. They have a special type of hemoglobin that absorbs oxygen very quickly at high altitudes, and their capillaries penetrate especially deep within their muscles to transfer oxygen to the muscle fibers
.
Other high flying birds include whooper swans, once observed by a pilot at 27,000 feet over the Atlantic between Iceland and Europe, and bar-tailed godwits (a shorebird), which have been seen at almost 20,000 feet. The record for North America is a mallard duck that collided with an airplane at 21,000 feet above Elko, Nevada in July, 1963. Most birds, though, fly lower--waterfowl typically at between 200-4,000 feet, and small songbirds at between 500-2,000 feet. However, the tiny Blackpoll warbler will fly up to 16,000 feet high in order to catch favorable winds on migration between Canada and South America. I'm not sure how well a sparrow would do, but similar-sized birds are quite capable of flying very high indeed. "
REF:
The Straight Dope: How high can birds and bees fly?