We describe the algorithms implemented in the first version of GRADSPH, a parallel, tree-based, smoothed particle hydrodynamics code for simulating self-gravitating astrophysical systems written in FORTRAN 90. The paper presents details on the implementation of the Smoothed Particle Hydro (SPH) description, where a gridless approach is used to model compressible gas dynamics. This is done in the conventional SPH way by means of 'particles' which sample fluid properties, exploiting interpolating kernels. The equations of self-gravitating hydrodynamics in the SPH framework are derived self-consistently from a Lagrangian and account for variable smoothing lengths ('GRAD-h') terms in both the hydrodynamic and gravitational acceleration equations. A Barnes-Hut tree is used for treating self-gravity and updating the neighbour list of the particles. In addition, the code updates particle properties on their own individual timesteps and uses a basic parallelisation strategy to speed up calculations on a parallel computer system with distributed memory architecture. Extensive tests of the code in one and three dimensions are presented. Finally, we describe the program organisation of the publicly available 3D version of the code, as well as details concerning the structure of the input and output files and the execution of the program.