Efficient and accurate techniques for simulation of soft tissue deformation are an increasingly valuable tool in many areas of medical image computing, such as biomechanically-driven image registration and interactive surgical simulation. For reasons of efficiency most analyses are based on simplified linear formulations, and previously almost all have ignored well established features of tissue mechanical response such as anisotropy and time-dependence. We address these latter issues by firstly presenting a generalised anisotropic viscoelastic constitutive framework for soft tissues, particular cases of which have previously been used to model a wide range of tissues. We then develop an efficient solution procedure for the accompanying viscoelastic hereditary integrals which allows use of such models in explicit dynamic finite element algorithms. We show that the procedure allows incorporation of both anisotropy and viscoelasticity for as little as 5.1% additional cost compared with the usual isotropic elastic models. Finally we describe the implementation of a new GPU-based finite element scheme for soft tissue simulation using the CUDA API. Even with the inclusion of more elaborate constitutive models as described the new implementation affords speed improvements compared with our recent graphics API-based implementation, and compared with CPU execution a speed up of 56.3 x is achieved. The validity of the viscoelastic solution procedure and performance of the GPU implementation are demonstrated with a series of numerical examples.