Experiments on vortex shedding from a cylinder placed in uniform flows of low concentration polymer solutions are reported for Reynolds numbers from 50 to 150. The fluids used were aqueous solutions of polyethylene oxide (PEO) and rheological characterization showed them to have a constant viscosity over a wide range of shear rates. Using the Zimm model relaxation time the Deborah numbers calculated for the cylinder wake are O(10-3). Parallel vortex shedding was induced with a combination of end-cylinders and end-plates and the resulting nominally two-dimensional cylinder wake was investigated using LDA, PIV, hydrogen bubble visualizations and hot film anemometry. The characteristics of the von Kármán instability are presented as a function of PEO concentration. It is shown that even small amounts of polymers, corresponding to low Deborah numbers, have a significant stabilizing effect which is only counteracted by shear-thinning at higher concentrations. The presence of PEO is also observed to reduce the saturated vortex shedding frequency and cause a redistribution of velocity fluctuations in the attached shear layers. Shear-thinning is found to decrease velocity fluctuations in the wake. Downstream of the cylinder a velocity overshoot is measured for the polymer solutions and an analogy is drawn to the negative wake behind a sphere falling in a viscoelastic fluid.