Originally posted by: Guntz
The earliest date I can find for Phantasy Star (SMS) is December 20 1987.
http://www.smspower.org/Games/PhantasyStar-SMS
Remember that Legend of Zelda was released for the Famicom Disk System in 1986, not Famicom cartridge. It wasn't until the NES version in 1987 that the game used battery + SRAM to save. Phantasy Star (or some other SMS game I can't think of) might predate Zelda, maybe not. It's hard finding release info on SMS games.
If there is a game that pre-dates Zelda I think it would have to be on a home computer or overseas system.
There may be a cartridge that saves for C-64 , Atari 800, TRS-80 etc but I'm fairly certain that there weren't any US console games with save function prior to NES.