We present a new algorithm which allows a radical increase in the computer enumeration of benzenoids b(h) with h hexagons. We obtain b(h) up to h = 35. We prove that b(h) approximately const.kappa(h), prove the rigorous bounds 4.789 < or = kappa < or = 5.905, and estimate that kappa = 5.16193016(8). Finally, we provide strong numerical evidence that the generating function summation operator b(h)z(h) approximately A(z) log(1 - kappa z), estimate A(1/kappa) and predict the subleading asymptotic behavior. We also provide compelling arguments that the mean-square radius of gyration <R(g)(2)>(h) of benzenoids of size h grows as h(2 nu), with nu = 0.64115(5).