This paper describes the construction of the largest gait database in the world and its application to a statistically reliable performance evaluation of vision-based gait recognition. Whereas existing gait databases include at most an order of a hundred subjects, we construct an even larger gait database which includes 1,035 subjects (569 males and 466 females) with ages ranging from 2 to 94 years. Because a sufficient number of subjects for each gender and age group are included in this very large-scale gait database, we can analyze the dependence of gait recognition performance on gender or age groups. The results of GEI-based gait recognition provide several novel insights, such as the tradeoff of gait recognition performance among age groups derived from the maturity of walking ability and physical strength. Moreover, improvement in the statistical reliability of performance evaluation is shown by comparing the gait recognition results for the whole set and subsets of a hundred subjects selected randomly from the whole set.