This paper studies the effect of delay costs on the travelers’ parking strategy under the random distribution of curbside parking spaces. Travelers have to decide how long in advance they should depart to arrive at the destination and how far away from the destination they should start looking for an available parking space. Their costs include not only the ordinary travel costs, but also expected cruising costs and delay costs depending on the real-time distribution of curbside parking spaces. Then three parking strategies are defined according to their different possible states of the delays when traveler reaches his / her destination. The “never-early-arrival”strategy is proved to be irrational , while both the “early-park-early-arrival ”strategy and the“early-park-late-arrival”strategy may be the optimal choice under different conditions. Typically, the“early-park-late-arrival”strategy is optimal if the unit time penalty of early arrival is no less than that of late arrival. Numerical results support the analytical propositions.