Paper Wheels received generally positive reviews from music critics. Stephen Thomas Erlewine of AllMusic said, "What Anastasio achieves with Paper Wheels is tricky -- he's made a jam band record with defined hooks and songs that neither dilutes his identity or compromises it -- but he makes it seem easy."[2]