A remote start control system is for a vehicle including a data communications bus extending through the vehicle, an engine, at least one vehicle brake being selectively operable based upon a parking brake command on the data communications bus, and a vehicle climate control system operable based upon a climate control command on data communications bus. The remote start control system may include a remote start transmitter to generate a remote start signal, and a vehicle remote start controller at the vehicle that may include a receiver to receive the remote start signal, and at least one processor cooperating with the receiver. The at least one processor, in response to the remote start signal, may generate the parking brake command on the data communications bus, generate the climate control command on the data communications bus, and start the engine.