Negative binomial distribution, despite seemingly obvious relation to binomial, is actually better compared against the Poisson distribution. All three are discrete, btw.
In practical applications, NB is an alternative to Poisson when you observe the dispersion (variance) higher than expected by Poisson. Poisson is a the first choice to consider when you deal with count data, e.g. an annual number of car accident fatalities in a small town. Poisson distribution's both mean and the variance are defined by one parameter - a rate of occurrence, usually denoted as $\lambda$. As long as you estimated $\lambda$, your mean and variance follow. In fact, the mean must be equal to variance.
If your data suggests that the variance is greater than the mean (overdispersion), this rules out Poisson, then Negative binomial would be a next distribution to look at. It has more than one parameter, so its variance can be greater than the mean.
The relation of NB to binomial comes from the underlying process, as it was described in @Jelsema's answer. The process are related, so the distributions are too, but as I explained here the link to Poisson distribution is closer in practical applications.
UPDATE:
Another aspect is the parameterization. Binomial distribution has two parameters: p and n. Its bona fide domain is 0 to n. In that it's not only discrete, but also defined on a finite set of numbers.
In contrast both Poisson and NB are defined on infinite set of non-negative integers. Poisson has one parameter $\lambda$, while NB has two: p and r. Note, that these two do not have parameter $n$. Thus it's one more way to see how NB and Poisson are connected.