We present a robust linear-scaling algorithm to compute the symmetric square-root or Lowdin decomposition of the atomic-orbital overlap matrix. The method is based on Newton-Schulz iterations with a new approach to starting matrices. Calculations on 12 chemically and structurally diverse molecules demonstrate the efficiency and reliability of the method. Furthermore, the calculations show that linear scaling is achieved.