We establish a necessary and sufficient criterion for the Fredholmness of a general locally compact band-dominated operator
A on
and solve the long-standing problem of computing its Fredholm index in terms of the limit operators of A. The results are applied to operators of convolution type with almost periodic symbol.