Many proteins exhibit dynamic activation patterns in the form of irregular pulses. Such behavior is typically attributed to a combination of positive and negative feedback loops in the underlying regulatory network. However, the presence of positive feedbacks is difficult to demonstrate unequivocally, raising the question of whether stochastic pulses can arise from negative feedback only. Here, we use the protein kinase A (PKA) system, a key regulator of the yeast pulsatile transcription factor Msn2, as a case example to show that irregular pulses of protein activity can arise from a negative feedback loop alone. Simplification to two variables reveals that a combination of zero-order ultrasensitivity, timescale separation between the activator and the repressor, and an effective delay in the feedback are sufficient to amplify a perturbation into a pulse. The same circuit topology can account for both activation and inactivation pulses, pointing toward a general mechanism of stochastic pulse generation.