PrV2Al20 is a rare example of a heavy-fermion system based on strong hybridization between conduction electrons and nonmagnetic quadrupolar moments of the cubic Γ3 ground doublet. Here, we report that a high-quality single crystal of PrV2Al20 exhibits superconductivity at Tc=50 mK in the antiferroquadrupole-ordered state under ambient pressure. The heavy-fermion character of the superconductivity is evident from the specific heat jump of ΔC/T∼0.3 J/mol K(2) and the effective mass m*/m0∼140 estimated from the temperature dependence of the upper critical field. Furthermore, the high-quality single crystals exhibit double transitions at TQ=0.75 K and T*=0.65 K associated with quadrupole and octupole degrees of freedom of the Γ3 doublet. In the ordered state, the specific heat C/T shows a T(3) dependence, indicating the gapless mode associated with the quadrupole order, the octupole order, or both. The strong sensitivity to impurity of the superconductivity suggests unconventional character due to significant quadrupolar fluctuations.