Using accurate multi-component diffusion treatment in numerical combustion studies remains formidable due to the computational cost associated with solving for diffusion velocities. To obtain the diffusion velocities, for low density gases, one needs to solve the Stefan-Maxwell equations along with the zero diffusion flux criteria, which scales as O(N3), when solved exactly. In this paper, we propose an accurate, fast, direct and robust algorithm to compute multi-component diffusion velocities. We also take into account the Soret effect, while computing the multi-component diffusion velocities. To our knowledge, this is the first provably accurate algorithm (the solution can be obtained up to an arbitrary degree of precision) scaling at a computational complexity of O(N) in finite precision. The key idea involves leveraging the fact that the matrix of the reciprocal of the binary diffusivities, V, is low rank, with its rank being independent of the number of species involved. The low rank representation of matrix V is computed in a fast manner at a computational complexity of O(N) and the Sherman-Morrison-Woodbury formula is used to solve for the diffusion velocities at a computational complexity of O(N). Rigorous proofs and numerical benchmarks illustrate the low rank property of the matrix V and scaling of the algorithm. © 2016 The Combustion Institute. Published by Elsevier Inc.