The classical Gaussian ensembles of random matrices can be constructed by maximizing Boltzmann-Gibbs-Shannon's entropy, S(BGS) = -integral dH[P(H)]ln[P(H)], with suitable constraints. Here, we construct and analyze random-matrix ensembles arising from the generalized entropy S(q) = [1- integral dH [P(H)](q)] /(q-1) (thus, S1 = S(BGS) ). The resulting ensembles are characterized by a parameter q measuring the degree of nonextensivity of the entropic form. Making q-->1 recovers the Gaussian ensembles. If q not equal 1, the joint probability distributions P(H) cannot be factorized, i.e., the matrix elements of H are correlated. In the limit of large matrices two different regimes are observed. When q<1, P(H) has compact support, and the fluctuations tend asymptotically to those of the Gaussian ensembles. Anomalies appear for q>1 : Both P(H) and the marginal distributions P( H(ij) ) show power-law tails. Numerical analyses reveal that the nearest-neighbor spacing distribution is also long-tailed (not Wigner-Dyson) and, after proper scaling, very close to the result for the 2 x 2 case--a generalization of Wigner's surmise. We discuss connections of these "nonextensive" ensembles with other non-Gaussian ones, such as the so-called Lévy ensembles and those arising from soft confinement.