What are some problems in the class P which we used to think were in the class of NP?
Consider the following problem $A$: given $n$, is $n$ a composite integer (i.e., not a prime)?

It is easy to prove that $A$ is in NP: any nontrivial divisor acts as a certificate. 

Proving that $A$ is also in P is much harder, and it is equivalent to proving that its complement, i.e. primality, is in P as well. Still, this has now been proved.