Updated December 2011

A consolidation of some information gathered from recent posts:

Updated 5/2012 to add in Hilton

Penn station
with an Amtrak or NJ Transit Ticket (Previous posts have said LIRR tickets are not acceptable)
31st street / 8th ave entrance, past the entrance for gates 1 to 4

Grand Central Terminal
No in station storage

Port Authority
No in station storage

JFK
Terminal 1 Arrivals - First floor (near Alitalia and Olympic Airlines)
Hours of Operation: 7AM-11PM
Telephone: (718) 751-2947

Terminal 3 Arrivals
Pre-Security
Arrivals
Hotels Counter in Area B

Terminal 4 Arrivals - First floor
Hours of Operation: 24 Hours
Telephone: (718) 751-4020

Edited 9/23/2010 - The Port Authority website lists storage at terminal 5, but as sbm12 indicates below this really isn't there, so I removed it. The Jet Blue website refers people to the facilities at Terminals 1 and 4.

Terminals 8 - (American Airlines)
Hours of Operation: 6AM-10PM
Approximate Cost (depending on size): $8 - $18 per day
Telephone: (718) 995-9292
Early (earlier that 6:00am) pick-up of luggage is possible.

LGA
No Storage

Newark
NBS in Terminal C, Carosel 1
1 (908) 933-0503

note - the NYC.com visitor guide for luggage storage says there is no storage at Newark, but as of December 15, 2011, kwildnj reported there is still luggage storage there, and that They are open 8:00am-1:00am daily. Fees are 10.00 First Bag, 5.00 Subsequent (per day)

Macy*s
There are many pages online saying that Macy*s will accept bags

Schwartz Travel
212.290.2626

355 w 36th St.
Between 8th & 9th Ave. – 2nd Floor
Close to MSG, Penn Station (West Side) & Port Authority A.C.E. Subway stop, next to the Wyndham Hotel
Open Everyday: 8am - 11pm

34 w 46th St.
Between 5th & 6th Ave. – 4th Floor
Close to Times Square & Grand Central Terminal Same Building as Via Brasil & Subway
Open Everyday: 8am - 11pm

2 w 32th St.
Between 5th Ave & Broadway – 5th Floor
Close to MSG, Penn Station (East Side) & the Empire State Building
(Located near 5th Ave. Next to the Nyma Hotel. Same building as the Korean Museam, OZ Hair, Kirakuya Sake Bar)
Now Closed - will re-open July 2012

Day . Week . Month Please send e-mail to reserve - Walk-ins Welcome. Storage Price: $7 - $10 each bag. $10 maximum per day per luggage. Monthly Rate: $2 to $5 a day, (depending on size) per luggage.Tourist Friendly - Special Group & Student Rates Safe . Secure . Reliable. Satisfaction Guaranteed

We are Open Everyday at 355 w 36th st included Major Holidays.

Near Yankee Stadium
In the Bronx across from Yankee Stadium at the bowling alley. They have a pretty good bag check.

Hilton Hotel
6th between 53 and 54th, Manhattan
I was there for a meeting this morning and noticed they have a luggage storage side on first floor just to the right of the main entrance as you face the hotel. Open 7 am to 10 pm, $3.50 per bag per calendar day. Says to ask the front desk after hours.