Shareholders' Equity (Deficit) (Schedule of Company's repurchase program) (Details) (USD $)
In Millions, except Share data in Thousands, unless otherwise specified
 12 Months Ended 24 Months Ended 0 Months Ended 12 Months Ended 24 Months Ended 12 Months Ended 1 Months Ended 12 Months Ended 2 Months Ended
Feb. 01, 2014
Feb. 02, 2013
Jan. 28, 2012
Feb. 01, 2014
November 2012 Repurchase Program [Member]
Feb. 02, 2013
November 2012 Repurchase Program [Member]
Feb. 01, 2014
November 2012 Repurchase Program [Member]
Nov. 12, 2012
February 2012 Repurchase Program [Member]
Feb. 02, 2013
February 2012 Repurchase Program [Member]
Feb. 02, 2013
November 2011 Repurchase Program [Member] [Member]
Jan. 28, 2012
November 2011 Repurchase Program [Member] [Member]
Feb. 02, 2013
November 2011 Repurchase Program [Member] [Member]
Jan. 28, 2012
May 2011 Repurchase Program [Member]
Jan. 28, 2012
March 2011 Repurchase Program [Member]
Mar. 31, 2011
November 2010 [Member]
Jan. 28, 2012
November 2010 [Member]
Mar. 21, 2014
Subsequent Event [Member]
November 2012 Repurchase Program [Member]
Feb. 01, 2014
Accounts Payable [Member]
November 2012 Repurchase Program [Member]
Feb. 02, 2013
Accounts Payable [Member]
November 2012 Repurchase Program [Member]
Stock Repurchase Program, Authorized Amount           $ 250 [1]   $ 500 [2]     $ 250 $ 500 $ 500   $ 200 [3]      
Treasury Stock, Shares, Acquired 1,377 13,773 32,535 1,377 245     9,871 3,657 2,116   13,293 13,695   3,431 300    
Repurchase of Common Stock 63 625 1,194 63 11     450 164 85   500 500   109 15    
Average Stock Price of Shares Repurchased within Program           $ 45.80   $ 45.61     $ 44.90 $ 37.59 $ 36.49   $ 31.68      
Share repurchase program, remaining balance       176     50             31        
Share repurchase reflected in Accounts payable                                 $ 3 $ 0
[1] The November 2012 repurchase program had $176 million remaining as of February 1, 2014.
[2] The February 2012 repurchase program had $50 million remaining at the time it was cancelled in conjunction with the approval of the November 2012 repurchase program.
[3] The November 2010 repurchase program had $31 million remaining at the time it was cancelled in conjunction with the approval of the March 2011 repurchase program.