Fredman, Sedgewick, Sleator, and Tarjan proposed the pairing heap as a self-adjusting, streamlined version of the Fibonacci heap. It provably supports all priority queue operations in logarithmic time and is known to be extremely efficient in practice. However, despite its simplicity and empirical superiority, the pairing heap is one of the few popular data structures whose basic complexity remains open. In this paper we prove that pairing heaps support the deletemin operation in optimal logarithmic time and all other operations (insert, meld, and decreasekey) in time O(2^2 \sqrt {\log \log n} ) This result gives the first sub-logarithmic time bound for decreasekey and comes close to the lower bound of \Omega (\log \log n) established by Fredman.