Goodwill and Long-Lived Assets - Long Lived Assets (Details) $ in Millions	3 Months Ended								12 Months Ended
	Jan. 30, 2016 USD ($)	Oct. 31, 2015 USD ($)	Aug. 01, 2015 USD ($)	May. 02, 2015 USD ($)	Jan. 31, 2015 USD ($) store	Nov. 01, 2014 USD ($)	Aug. 02, 2014 USD ($)	May. 03, 2014 USD ($)	Jan. 30, 2016 USD ($)	Jan. 31, 2015 USD ($) store	Feb. 01, 2014 USD ($)
Finite-Lived Intangible Assets [Line Items]
Impairment of long-lived assets related to store closures									$ 50	$ 60
Impairment of long-lived assets									22	23
Impairment of long-lived assets- technology assets	$ 25	$ 2	$ 1	$ 22	$ 434	$ 9	$ 5	$ 22	50	470	$ 0
Gross Carrying Amount	709				709				709	709
Accumulated Amortization	(435)				(374)				(435)	(374)
Intangible assets, net	274				335				274	335
Customer relationships [Member]
Finite-Lived Intangible Assets [Line Items]
Gross Carrying Amount	628				628				628	628
Accumulated Amortization	(411)				(364)				(411)	(364)
Intangible assets, net	217				264				217	264
Technology [Member]
Finite-Lived Intangible Assets [Line Items]
Gross Carrying Amount	72				72				72	72
Accumulated Amortization	(20)				(6)				(20)	(6)
Intangible assets, net	52				66				52	66
Tradenames [Member]
Finite-Lived Intangible Assets [Line Items]
Gross Carrying Amount	9				9				9	9
Accumulated Amortization	(4)				(4)				(4)	(4)
Intangible assets, net	$ 5				$ 5				5	5
International Operations [Member]
Finite-Lived Intangible Assets [Line Items]
Impairment of long-lived assets									15	1
North American Stores & Online [Member]
Finite-Lived Intangible Assets [Line Items]
Impairment of long-lived assets									7	22
Impairment of long-lived assets- technology assets									22
2014 Restructuring Plan [Member]
Finite-Lived Intangible Assets [Line Items]
Impairment of long-lived assets related to store closures										$ 37
Approved store closures through 2015 | store					225					225
Planned Pre-Tax Cost Savings					$ 500					$ 500
2014 Restructuring Plan [Member] | International Operations [Member]
Finite-Lived Intangible Assets [Line Items]
Impairment of long-lived assets related to store closures										1
2014 Restructuring Plan [Member] | North American Stores & Online [Member]
Finite-Lived Intangible Assets [Line Items]
Impairment of long-lived assets related to store closures									6	36
Impairment of long-lived assets- technology assets									$ 6	$ 37