© 2016. The American Astronomical Society. All rights reserved. In area and depth, the Pan-STARRS1 (PS1) 3π survey is unique among many-epoch, multi-band surveys and has enormous potential for the all-sky identification of variable sources. PS1 has observed the sky typically seven times in each of its five bands (grizy) over 3.5 years, but unlike SDSS, not simultaneously across the bands. Here we develop a new approach for quantifying statistical properties of non-simultaneous, sparse, multi-color light curves through light curve structure functions, effectively turning PS1 into a ∼35-epoch survey. We use this approach to estimate variability amplitudes and timescales (ωr, τ) for all point sources brighter than rP1 = 21.5 mag in the survey. With PS1 data on SDSS Stripe 82 as "ground truth," we use a Random Forest Classifier to identify QSOs and RR Lyrae based on their variability and their mean PS1 and WISE colors. We find that, aside from the Galactic plane, QSO and RR Lyrae samples of purity ∼75% and completeness ∼92% can be selected. On this basis we have identified a sample of ∼1,000,000 QSO candidates, as well as an unprecedentedly large and deep sample of ∼150,000 RR Lyrae candidates with distances from ∼10 to ∼120 kpc. Within the Draco dwarf spheroidal, we demonstrate a distance precision of 6% for RR Lyrae candidates. We provide a catalog of all likely variable point sources and likely QSOs in PS1, a total of 25.8 × 106 sources.