It has been assumed that abnormal functional connections (FCs) critically underlie the neural mechanism of autism spectrum disorder (ASD). Currently, its diagnosis is dependent on medial interviews using standard clinical scales, designed to identify ASD-specific impairments in socio-communication and behavioral flexibility. There has been no effective neurally-defined biomarker that could be used in clinical settings for reliable, quantitative assessment on the behavioral symptoms of ASD. Here, we adopted a data-driven, hypothesis-free approach and investigated the whole-brain patterns of FCs using a resting-state functional connectivity magnetic resonance imaging (rs-fcMRI) data of 74 adults with ASD and 114 demographically-matched typically-developed individuals acquired at multiple sites in Japan. By employing novel machine learning algorithms, we established an rs-fcMRI-based classifier that incorporated a small fraction (0.2%) of all the FCs considered in the whole brain. This classifier allowed accurate prediction on the diagnoses of the individuals in the data set (84% correct) and this reliability was generalized to the second cohort comprising of ethnically different populations in the US (74% correct). Furthermore, the same set of FCs in the classifier accurately predicted the sub-scores of standard diagnostic instruments (ADI-R and ADOS) that described the behavioral characteristics of individuals with ASD in childhood and at present, respectively. Collectively, we have established a reliable rs-fcMRI-based biomarker of ASD that elucidates a direct link between the underlying neural mechanisms and the behavioral characteristics of ASD.