It is well known that the Poiseuille flow of a visco-elastic polymer fluid between plates or through a tube is linearly stable in the zero Reynolds number limit, although the stability is weak for large Weissenberg numbers (Wi). In this paper, we argue that recent experimental and theoretical work on the instability of visco-elastic fluids in Taylor-Couette cells and numerical work on channel flows suggest a scenario in which Poiseuille flow of visco-elastic polymer fluids exhibits a nonlinear "subcritical" instability due to normal stress effects, with a threshold which decreases for increasing Weissenberg number. This proposal is confirmed by an explicit weakly nonlinear stability analysis for Poiseuille flow of an UCM fluid. Our analysis yields explicit predictions for the critical amplitude of velocity perturbations beyond which the flow is nonlinearly unstable, and for the wavelength of the mode whose critical amplitude is smallest. The nonlinear instability sets in quite abruptly at Weissenberg numbers around 4 in the planar case and about 5.2 in the cylindrical case, so that for Weissenberg numbers somewhat larger than these values perturbations of the order of a few percentage in the wall shear stress suffice to make the flow unstable. We have suggested elsewhere that this nonlinear instability could be an important intrinsic route to melt fracture and that preliminary experiments are both qualitatively and quantitatively in good agreement with these predictions. (C) 2004 Elsevier B.V. All rights reserved.