The origins of the nearly one billion people inhabiting the Indian subcontinent and following the customs of the Hindu caste system are controversial: are they largely derived from Indian local populations (i.e. tribal groups) or from recent immigrants to India? Archaeological and linguistic evidence support the latter hypothesis, whereas recent genetic data seem to favor the former hypothesis. Here, we analyze the most extensive dataset of Indian caste and tribal Y chromosomes to date. We find that caste and tribal groups differ significantly in their haplogroup frequency distributions; caste groups are homogeneous for Y chromosome variation and more closely related to each other and to central Asian groups than to Indian tribal or any other Eurasian groups. We conclude that paternal lineages of Indian caste groups are primarily descended from Indo-European speakers who migrated from central Asia approximately 3,500 years ago. Conversely, paternal lineages of tribal groups are predominantly derived from the original Indian gene pool. We also provide evidence for bidirectional male gene flow between caste and tribal groups. In comparison, caste and tribal groups are homogeneous with respect to mitochondrial DNA variation, which may reflect the sociocultural characteristics of the Indian caste society.