We show (via 3D spectral anelastic hydrodynamic simulations) that finite-amplitude perturbations in a stably stratified protoplanetary disk lead to the natural formation of 3D, long-lived, coherent vortices. This is in contrast to previous 3D constant density studies that showed that perturbations to Keplerian shear always rapidly decay. Our results are also entirely distinct from the numerous 2D studies of vortex dynamics in the midplane of Keplerian disks: We show that vortices in the midplane are linearly unstable with an e-folding time of only a few orbital periods; the nonlinear development of the instability leads to the destruction of vortices in the midplane. In our numerical simulations, a midplane vortex (prior to its destruction) was a source of perturbations: as it oscillated, it excited internal gravity waves which would propagate away from the midplane, break, and create vorticity (a baroclinic effect). The regions of vorticity above and below the midplane would coalesce into new vortices. Whereas the midplane vortex would eventually succumb to the instability, the off-midplane vortices were stable (to infinitesimal and finite-amplitude perturbations) and long-lived. The key ingredient for stable 3D vortices is stable stratification: the vertical component of protostellar gravity vanishes in the midplane, so the gas is unstratified there; off the midplane, the magnitudes of gravity and stratification increase linearly with height. Stable, 3D off-midplane vortices may play two key roles in star and planet formation: in cool, nonmagnetized disks, vortices may transport angular momentum outward so that mass can continue to accrete onto the growing protostar; and vortices rapidly sweep-up and concentrate dust particles, which may help in the formation of planetesimals, the basic ``building blocks'' of planets, either by increasing the efficiency of binary agglomeration, or be seeding a local gravitational instability.