Histone deacetylase inhibitors (HDACIs) strengthen memory following fear conditioning and cocaine-induced conditioned place preference. Here, we examined the effects of two nonspecific HDACIs, valproic acid (VPA) and sodium butyrate (NaB), on appetitive learning measured by conditioned stimulus (CS)-induced reinstatement of operant responding. Rats were trained to lever press for food reinforcement and then injected with VPA (50-200 mg/kg, i.p.), NaB (250-1000 mg/kg, i.p.), or saline vehicle (1.0 ml/kg), 2 h before receiving pairings of noncontingent presentation of food pellets preceded by a tone+light cue CS. Rats next underwent extinction of operant responding followed by response-contingent re-exposure to the CS. Rats receiving VPA (100 mg/kg) or NaB (1000 mg/kg) before conditioning displayed significantly higher cue-induced reinstatement than did saline controls. Rats that received either vehicle or VPA (100 mg/kg) before a conditioning session with a randomized relation between presentation of food pellets and the CS failed to show subsequent cue-induced reinstatement with no difference between the two groups. These findings indicate that, under certain contexts, HDACIs strengthen memory formation by specifically increasing the associative strength of the CS, not through an increasing motivation to seek reinforcement.