A fuel injection pump in which a relief channel is formed which communicates with the pump working chamber and is arranged to be blocked by a valve means, associated with a valve actuating means responsive to a pressure varying with engine r.p.m., during starting of the engine so that the fuel injection quantity is increased. Thus, improved starting characteristics of the engine can be obtained. Said relief channel may comprise a first channel communicating with the pump working chamber, and a second relief channel which has a portion thereof extending in the pump plunger to terminate in an outer periphery of the bottom end of said plunger and is so disposed as to communicate with the pump suction chamber after a predetermined delivery stroke length or prestroke has been executed. Communication between said first and second relief channels is adapted to be interrupted by said valve means at less than a predetermined engine r.p.m. As another advantageous arrangement, the relief channel may comprise a first relief channel which includes a port having one end communicating with the pump working chamber and the other end terminating in an outer periphery of the plunger and a communication channel having one end terminating in an inner periphery of the plunger barrel and the other end arranged for communication with a lower pressure zone, and a second relief channel allowing a restricted flow rate and communicating with the pump working chamber. The port and communication channel of said first relief channel are so disposed as to communicate with each other at the beginning of the delivery stroke of the plunger. Said first and second relief channels are arranged to be simultaneously blocked by said valve means during starting of the engine.