Pulsar surveys with the SKA will discover tens of thousands of pulsars, amongst which we expect to find a pulsar in orbit around a stellar-mass black hole and pulsars in close orbit around the super-massive black hole at the Galactic Centre. Thousands of millisecond pulsars will form an immense pulsar timing array to detect primordial gravitational waves. These can be used to provide unique tests of gravity and General Relativity in the strong-field regime.