Self-gravitating gaseous filaments exist on many astrophysical scales , from sub-pc filaments in the interstellar medium to Mpc scale streams feeding galaxies from the cosmic web . These filaments are often subject to Kelvin-Helmholtz Instability ( KHI ) due to shearing against a confining background medium . We study the nonlinear evolution of KHI in pressure-confined self-gravitating gas streams initially in hydrostatic equilibrium , using analytic models and hydrodynamic simulations , not including radiative cooling . We derive a critical line-mass , or mass per unit length , as a function of the stream Mach number and density contrast with respect to the background , \mu _ { cr } ( M _ { b } , \delta _ { c } ) \leq 1 , where \mu = 1 is normalized to the maximal line mass for which initial hydrostatic equilibrium is possible . For \mu < \mu _ { cr } , KHI dominates the stream evolution . A turbulent shear layer expands into the background and leads to stream deceleration at a similar rate to the non-gravitating case . However , with gravity , penetration of the shear layer into the stream is halted at roughly half the initial stream radius by stabilizing buoyancy forces , significantly delaying total stream disruption . Streams with \mu _ { cr } < \mu \leq 1 fragment and form round , long-lived clumps by gravitational instability ( GI ) , with typical separations roughly 8 times the stream radius , similar to the case without KHI . When KHI is still somewhat effective , these clumps are below the spherical Jeans mass and are partially confined by external pressure , but they approach the Jeans mass as \mu \rightarrow 1 and GI dominates . We discuss potential applications of our results to streams feeding galaxies at high redshift , filaments in the ISM , and streams resulting from tidal disruption of stars near the centres of massive galaxies .