We probe the transport properties in protein solutions stable with respect to any, solid or liquid, phase separation as a step in the understanding of transport in the cytosol of live cells. We determine the mean squared displacement of probe particles in the time range 1 millisecond - 10 seconds in solutions of a model protein. The tested solutions exhibit significant elasticity at high frequencies, while at low frequencies, they are purely viscous. We attribute this viscoelasticity to a dense network of weakly-bound chains of protein molecules with characteristic lifetime of 10-100 ms. The found intrinsic viscoelasticity of protein solutions should be considered in biochemical kinetics models.