A remote start system is for a vehicle including an ignition switch sequentially movable to a plurality of switch positions, and a plurality of ignition switch wires coupled to the ignition switch. The remote start system may include a wiring harness having a plurality of remote start wires to be arbitrarily coupled to the plurality of ignition wires, a wireless receiver responsive to a wireless remote start signal, and a controller coupled to the wiring harness and the wireless receiver. The controller may, in a learning mode, perform a mapping of the remote start wires to the ignition wires based upon sequential movement of the ignition switch to the plurality of switch positions. The controller may, in an operating mode, selectively activate the remote start wires based upon the mapping to remote start an engine of the vehicle responsive to the wireless receiver.