The right to exercise early can only add value, so the premium is never negative — but it is usually tiny. It becomes material in two cases: deep in-the-money calls facing a large dividend, and deep in-the-money puts when interest on the strike proceeds outweighs the remaining extrinsic-value.
For a seller the premium is the price of accepting early-assignment risk. For a buyer it is money spent on an option that will rationally be exercised early only in narrow circumstances. Either way, it explains why an equity option and an index option on the same exposure do not price identically.
Example: XYZ has collapsed to $30 and you hold the $40 put with 60 days left and rates at 5%. A European version of that contract is worth $9.72, because you would have to wait two months for the $40. The American contract can be exercised today for $10.00, so it cannot be worth less than that. The $0.28 difference is the American premium.
Related: american-style-option, early-exercise, early-exercise-boundary, parity