Let $\pi (x)$ be the number of prime numbers less than or equal to $x$.
Euclid's proof of the infinitude of primes gives a horrible lower bound of the type $ \pi (x)>> \sqrt{\log{x}} $. Somewhat surprisingly, Euler's proof of the divergence of the sum of reciprocals of primes only gives $ \pi (x)>> \log{x}$ (see problem 8 of http://www.math.uiuc.edu/~hildebr/531.fall05/hw3.pdf).
Was anybody able to get a lower bound better than $\log{x}$ before Chebyshev got the order of magnitude right in ~ 1850?