We present spectroscopic observations of galaxies in 4 clusters at z = 0.7-0.8 and in one cluster at z similar to 0.5 obtained with the FORS2 spectrograph on the VLT as part of the ESO Distant Cluster Survey (EDisCS), a photometric and spectroscopic survey of 20 intermediate to high redshift clusters. We describe our target selection, mask design, observation and data reduction procedures, using these first 5 clusters to demonstrate how our strategies maximise the number of cluster members for which we obtain spectroscopy. We present catalogues containing positions, I-band magnitudes and spectroscopic redshifts for galaxies in the fields of our 5 clusters. These contain 236 cluster members, with the number of members per cluster ranging from 30 to 67. Our spectroscopic success rate, i.e. the fraction of spectroscopic targets which are cluster members, averages 50% and ranges from 30% to 75%. We use a robust biweight estimator to measure cluster velocity dispersions from our spectroscopic redshift samples. We also make a first assessment of substructure within our clusters. The velocity dispersions range from 400 to 1100 km s super(-1). Some of the redshift distributions are significantly non-Gaussian and we find evidence for significant substructure in two clusters, one at z similar to 0.79 and the other at z similar to 0.54. Both have velocity dispersions exceeding 1000 km s super(-1) but are clearly not fully virialised; their velocity dispersions may thus be a poor indicator of their masses. The properties of these first 5 EDisCS clusters span a wide range in redshift, velocity dispersion, richness and substructure, but are representative of the sample as a whole. Spectroscopy for the full dataset will allow a comprehensive study of galaxy evolution as a function of cluster environment and redshift.