Your transistor was connected as an emitter-follower. Its max output voltage was the output voltage from the PIC (+5V) minus the 0.7V base-emitter voltage of the transistor. The 12V relay won't operate with only 4.3V on its coil.
With the transistor's emitter grounded and the coil of the relay at its collector then the coil gets about 11.8V so the relay works properly.
When the relay is turned off, the inductance of its coil creates a very high voltage that can destroy the transistor. The diode arrests the high voltage.