Gaussian processes provide a framework for nonlinear nonparametric Bayesian\ninference widely applicable across science and engineering. Unfortunately,\ntheir computational burden scales cubically with the training sample size,\nwhich in the case that samples arrive in perpetuity, approaches infinity. This\nissue necessitates approximations for use with streaming data, which to date\nmostly lack convergence guarantees. Thus, we develop the first online Gaussian\nprocess approximation that preserves convergence to the population posterior,\ni.e., asymptotic posterior consistency, while ameliorating its intractable\ncomplexity growth with the sample size. We propose an online compression scheme\nthat, following each a posteriori update, fixes an error neighborhood with\nrespect to the Hellinger metric centered at the current posterior, and greedily\ntosses out past kernel dictionary elements until its boundary is hit. We call\nthe resulting method Parsimonious Online Gaussian Processes (POG). For\ndiminishing error radius, exact asymptotic consistency is preserved (Theorem\n1(i)) at the cost of unbounded memory in the limit. On the other hand, for\nconstant error radius, POG converges to a neighborhood of the population\nposterior (Theorem 1(ii))but with finite memory at-worst determined by the\nmetric entropy of the feature space (Theorem 2). Experimental results are\npresented on several nonlinear regression problems which illuminates the merits\nof this approach as compared with alternatives that fix the subspace dimension\ndefining the history of past points.\n