In this paper we show that two-dimensional nearest neighbor queries can be answered in optimal (O(log n)) time while supporting insertions in (O(log^{1+\epsilon}n)) time. No previous data structure was known that supports (O(log n))-time queries and polylog-time insertions. In order to achieve logarithmic queries our data structure uses a new technique related to fractional cascading that leverages the inherent geometry of this problem. Our method can be also used in other semi-dynamic scenarios.