High prevalence of STH leads to malnutrition, anemia, cognitive impairment, and growth disorders. Triple-dose albendazole 400 mg is a broad-spectrum anthelminthic; however, its effectiveness varies in every region. This study aims to determine the benefits of deworming using triple-dose albendazole on children's nutritional status in Perobatang Village, Southwest Sumba, Indonesia. This pre-post study was conducted in July 2016 and January 2017. Children aged 1-15 years were asked to collect stool for diagnosis of STH infection (Kato-Katz method), were measured for anthropometry status to obtain the nutritional status, and took albendazole 400 mg for three consecutive days. Data was analyzed with SPSS version 20. Prevalence of STH prior to the treatment was 95.4%: T. trichiura 85.2%, A. lumbricoides 71.6%, and hookworm 18.2%. After treatment, prevalence of STH decreased significantly (McNemar test, p < 0.001) to 53.4%, (T. trichiura 39.8%, A. lumbricoides 22.7%, and hookworm 1.1%). Before treatment, 33% participants were in normal nutritional status, 47.7% underweight, and 19.3% severely underweight. After treatment, children in normal nutritional status increased to 75%, underweight children decreased to 25%, and there were no severely underweight children. In conclusion, deworming with triple-dose albendazole 400 mg is effective in improving the nutritional status of children in Perobatang Village.