This study presents the first directly dated physical evidence of crop remains from the Early Neolithic archaeological layers in Taiwan. Systematic sampling and analysis of macro-plant remains suggested that Neolithic farmers at the Zhiwuyuan (Botanical Garden) site in Taipei, northern Taiwan, had cultivated rice and foxtail millet together at least 4,500 years ago. A more comprehensive review of all related radiocarbon dates suggests that agriculture emerged in Taiwan around 4,800–4,600 cal. BP, instead of the previous claim of 5,000 cal. BP. According to the rice grain metrics from three study sites of Zhiwuyuan, Dalongdong, and Anhe, the rice cultivated in northern and western-central Taiwan was mainly a short-grained type of the japonica subspecies, similar to the discoveries from the southeast coast of mainland China and the middle Yangtze valley. These new findings support the hypothesis that the southeast coast of mainland China was the origin of proto-Austronesian people who brought their crops and other cultural traditions across the Taiwan Strait 4,800 years ago and eventually farther into Island Southeast Asia.