My Macbook Air 13" Mid 2012 says I have to 'service battery'.

Cycle count is only part of the story. A MacBook battery can be "killed" in far less than 300 recharge cycles if you don't follow the guidance:

http://www.apple.com/uk/batteries/notebooks.html

e.g. keeping it on mains all the time, keeping it in hot, very cold or damp environments, or letting it repeatedly drop below 15% charge (or worse still, letting it go completely flat) will significantly reduce battery life.

Take it in to Apple for a free estimate. If you believe you have followed Apple's guidance on battery usage, then see if they will give you a discount on a replacement if it needs a new battery.

If Apple determines the battery at fault they will replace it for free.

themachead wrote:

If Apple determines the battery at fault they will replace it for free.

Nope... not without AppleCare.

baukje wrote:

I've had it for a bit more than a year

I sit corrected - I was under the impression that Federal law required them replace defective LIon batteries (fire hazard). I see even a defective battery under extended warranty can cost $50.00. This is a surprise, and, a disappointment.

Oh, I agree.

Same MBA, same issue. it started when i upgraded it to Mavericks and after that my battery was never the same again. :-(

I think you'd better make Genius Bar reservation and tell them about your problem.