We consider scalar conservation laws with nonlocal diffusion of Riesz–Feller type such as the fractal Burgers equation. The existence of traveling wave solutions with monotone decreasing profile has been established recently (in special cases). We show the local asymptotic stability of these traveling wave solutions in a Sobolev space setting by constructing a Lyapunov functional. Most importantly, we derive the algebraic-in-time decay of the norm of such perturbations with explicit algebraic-in-time decay rates.