Metacritic gave "North Star Deserter" a score of 77 (generally favorable reviews). The music review online magazinePitchfork Media gave North Star Deserter a 7.6 stating:
Chesnutt's voice remains the most curious instrument on North Star Deserter: His creaky vocals and peculiar pronunciation (which can locate unknown syllables in common words) may have diminished slightly since his first few Texas Hotel albums, but he sounds ornery as ever on North Star Deserter. On "Glossolalia" he spits sharply alliterative b's and d's, matching them to the percussively plucked strings as if warning you to back off. And yet he draws you in: On "Splendid", he sings, "We came across an incomplete set of..." He pauses ominously to make you lean forward and listen for the next words. That sense of mystery has served Chesnutt well over the course of a bumpy seventeen-year career. "Can't say I didn't rattle the load," he sings on closer "Rattle", "but I'm keeping it on the road."