The theory of large deviations constitutes a mathematical cornerstone in the foundations of Boltzmann-Gibbs statistical mechanics, based on the additive entropy $S_{BG}=- k_Bsum_{i=1}^W p_i ln p_i$. Its optimization under appropriate constraints yields the celebrated BG weight $e^{-beta E_i}$. An elementary large-deviation connection is provided by $N$ independent binary variables, which, in the $Ntoinfty$ limit yields a Gaussian distribution. The probability of having $n e N/2$ out of $N$ throws is governed by the exponential decay $e^{-N r}$, where the rate function $r$ is directly related to the relative BG entropy. To deal with a wide class of complex systems, nonextensive statistical mechanics has been proposed, based on the nonadditive entropy $S_q=k_Bfrac{1- sum_{i=1}^W p_i^q}{q-1}$ ($q in {cal R}; ,S_1=S_{BG}$). Its optimization yields the generalized weight $e_q^{-beta_q E_i}$ ($e_q^z equiv [1+(1-q)z]^{1/(1-q)};,e_1^z=e^z)$. We numerically study large deviations for a strongly correlated model which depends on the indices $Q in [1,2)$ and $gamma in (0,1)$. This model provides, in the $Ntoinfty$ limit ($forall gamma$), $Q$-Gaussian distributions, ubiquitously observed in nature ($Qto 1$ recovers the independent binary model). We show that its corresponding large deviations are governed by $e_q^{-N r_q}$ ($propto 1/N^{1/(q-1)}$ if $q>1$) where $q= frac{Q-1}{gamma (3-Q)}+1 ge 1$. This $q$-generalized illustration opens wide the door towards a desirable large-deviation foundation of nonextensive statistical mechanics.