Related Party Transactions (Details) (USD $) In Millions, except Share data, unless otherwise specified	12 Months Ended
	Feb. 02, 2013	Jan. 28, 2012	Jan. 29, 2011
Related Party Transactions
Expenses recognized	$ 13	$ 13	$ 14
Long-term debt held	3,041	3,490
Bain Capital Partners, LLC | Printing of circular advertisement services received from an external vendor
Related Party Transactions
Expenses recognized		6	39
Bain Capital Partners, LLC | Print procurement services received from an external vendor
Related Party Transactions
Expenses recognized	5	5
The Blackstone Group | Senior secured term loan
Related Party Transactions
Long-term debt held	30
The Blackstone Group | Store inventory counting services received from an external vendor
Related Party Transactions
Expenses recognized	6	6	6
The Blackstone Group | Candy-type items in stores received from an external vendor
Related Party Transactions
Expenses recognized	24	20	19
The Blackstone Group | Hospitality services received from an external vendor
Related Party Transactions
Expenses recognized	1	1	1
The Blackstone Group | Lease services of certain properties from a vendor
Related Party Transactions
Expenses recognized	5	3
The Sponsors
Related Party Transactions
Annual management fees	12
Highfields Capital Management LP
Related Party Transactions
Annual management fees	$ 1
Officers no longer with the company
Related Party Transactions
Number of shares repurchased	14,667	192,001