Polyelectrolyte complexes, PECs, are formed spontaneously by the interaction of oppositely charged polyelectrolytes. When hydrated, PECs are tough, elastic, biocompatible materials, but when dry they are hard and brittle. In either form, PECs have long been considered “unprocessable”. Here, we show that PECs are transformed from brittle to tough (when dry) by extrusion into highly strained fibers. Partial molecular strain in dry fibers may be relaxed by exposure to solutions of salt or hot water under a salt/temperature equivalence. Efficient shape memory of a complex strained in hot water is possible by cooling and recovering the original shape later in hot water.