Plants generally possess a strong ability to regenerate organs; for example, in tissue culture, shoots can regenerate from callus, a clump of actively proliferating, undifferentiated cells. Processing of pre-mRNA and ribosomal RNAs is important for callus formation and shoot regeneration. However, our knowledge of the roles of RNA quality control via the nonsense-mediated mRNA decay (NMD) pathway in shoot regeneration is limited. Here, we examined the shoot regeneration phenotypes of the low-beta-amylase1 (lba1)/upstream frame shift1-1 (upf1-1) and upf3-1 mutants, in which the core NMD components UPF1 and UPF3 are defective. These mutants formed callus from hypocotyl explants normally, but this callus behaved abnormally during shoot regeneration: the mutant callus generated numerous adventitious root structures instead of adventitious shoots in an auxin-dependent manner. Quantitative RT-PCR and microarray analyses showed that the upf mutations had widespread effects during culture on shoot-induction medium. In particular, the expression patterns of early auxin response genes, including those encoding AUXIN/INDOLE ACETIC ACID (AUX/IAA) family members, were significantly affected in the upf mutants. Also, the upregulation of shoot apical meristem-related transcription factor genes, such as CUP-SHAPED COTYLEDON1 (CUC1) and CUC2, was inhibited in the mutants. Taken together, these results indicate that NMD-mediated transcriptomic regulation modulates the auxin response in plants and thus plays crucial roles in the early stages of shoot regeneration.