We consider the effect of Anderson acceleration (AA) on the convergence order of nonlinear solvers in fixed point form $x_{k+1}=g(x_k)$, that are looking for a fixed point of g. While recent work has answered the fundamental question of how AA affects the convergence rate of linearly converging fixed point iterations (at a single step), no analytical results exist (until now) for how AA affects the convergence order of solvers that do not converge linearly. We first consider AA applied to general methods with convergence order r, and show that AA changes the convergence order to (at least) (r+1)/2 for depth m=1; a more complicated expression for the order is found for the case of larger m. This result is valid for superlinearly converging methods and also locally for sublinearly converging methods where r<1 locally but r$\rightarrow$1 as the iteration converges, revealing that AA asymptotically slows convergence for superlinearly converging methods but (locally) accelerates it for sublinearly converging methods. We then consider AA-Newton, and find that it is a special case that fits in the framework of the recent theory for linearly converging methods which allows us to deduce that depth level m reduces the asymptotic convergence order. Several numerical tests illustrate our theoretical results, including a significant acceleration of a Picard solver for a Bingham model of viscoplastic flow.