Altered function of the ubiquitin pathway has been implicated in the etiology of neurodegeneration. For example, gracile axonal dystrophy (gad) mutant mice, which harbor a deletion within the gene encoding ubiquitin C-terminal hydrolase L1 (Uch-L1), display sensory ataxia followed by posterior paralysis and lethality. We previously showed that mice homozygous for a targeted deletion of the related Uch-L3 gene are indistinguishable from wild-type. To assess whether the two hydrolases have redundant function, we generated mice homozygous for both Uch-L1gad and Uch-L3Delta3-7. The double homozygotes weigh 30% less than single homozygotes and display an earlier onset of lethality, possibly due to dysphagia, a progressive loss in the ability to swallow food. This is consistent with histological analysis that revealed axonal degeneration of the nucleus tractus solitarius (NTS) and area postrema (AP) of the medulla. The NTS is essential for central nervous system control of swallowing. The double homozygotes also display a more severe axonal degeneration of the gracile tract of the medulla and spinal cord than had been observed in Uch-L1gad single homozygotes. In addition, degeneration of dorsal root ganglia cell bodies was detected in both the double homozygotes and Uch-L3Delta3-7 single homozygotes. Given that both Uch-L1gad and Uch-L3Delta3-7 single homozygotes display distinct degenerative defects that are exacerbated in the double homozygotes, we conclude that Uch-L1 and Uch-L3 have both separate and overlapping functions in the maintenance of neurons of the gracile tract, NTS and AP. This study is the first to successfully document dysphagia in the mouse and is a potentially valuable resource for understanding human neurodegenerative disorders that cause swallowing defects.