Passerine birds from two late Pliocene localities, Shaamar in northern Mongolia and Beregovaya in Transbaikalia (East Russia), represent the first known Neogene fossil assemblages of perching birds from Asia. A total of 11 families and 15 taxa are recognized, including a new genus and species of bunting, Pliocalcarius orkhonensis, apparently related to the Longspurs, and new species within the genera Hirundo and Rhodospiza, which are described. The avifauna is composed of open land and bush dwellers; it contains a few arid species, representing the oldest finds of the corresponding genera or lineages. This may indicate that the living Asian arid avian complex originated in Central Asia in the Neogene. Several genera (Rhodospiza, Paradoxornis) are documented in this paper for the first time in pre-Pleistocene deposits. Report of Calcarius is the first pre-Holocene evidence of the occurrence of this genus in Asia, which together with the remains of Synaptomys lemmings at Shaamar, illustrates faunal interchanges between North America and Asia in the Pliocene.