<PAGE>
 
                                                                  EXHIBIT 10.5.3
 
                                AMENDMENT NO. 3


     THIS AMENDMENT NO. 3 (this "Amendment"), dated as of March 24, 1999, to the
                                 ---------                                      
Credit Agreement referenced below, is by and among JUST FOR FEET, INC., a
Delaware corporation (the "Borrower"), the subsidiaries and affiliates of the
                           --------                                          
Borrower identified on the signature pages hereto (the "Guarantors"), the
                                                        ----------       
lenders identified on the signature pages hereto (the "Lenders") and
                                                       -------      
NATIONSBANK, N.A., as Administrative Agent (in such capacity, the
                                                                 
"Administrative Agent").  Terms used but not otherwise defined shall have the
 --------------------                                                        
meanings provided in the Credit Agreement.

                              W I T N E S S E T H

     WHEREAS, a $200 million credit facility has been extended to the Borrower
pursuant to the terms of that Credit Agreement dated as of December 10, 1998 (as
amended and modified, the "Credit Agreement") among the Borrower, the
                           ----------------                          
Guarantors, the Lenders, Compass Bank, as Documentation Agent, First Union
National Bank, Marine Midland Bank, SouthTrust Bank, N.A. and SunTrust Bank,
Atlanta, as Co-Agents, and NationsBank, N.A., as Administrative Agent;

     WHEREAS, the Borrower has made arrangements to issue up to $250 million in
Senior Subordinated Notes;

     WHEREAS, the Borrower has requested certain modifications to the Credit
Agreement in connection with the issuance of the Senior Subordinated Notes and
such modifications require the consent of the Required Lenders;

     WHEREAS, the Required Lenders have agreed to the requested modifications on
the terms and conditions set forth herein;

     NOW, THEREFORE, IN CONSIDERATION of the premises and other good and
valuable consideration, the receipt and sufficiency of which is hereby
acknowledged, the parties agree as follows:

     1.  The Credit Agreement is amended in the following respects:

     1.1  In Section 1.1 of the Credit Agreement, the following definitions are
     amended or added to read as follows:

             "Consolidated Senior Funded Debt" means Consolidated Funded Debt
              -------------------------------  
          less Subordinated Debt.

             "Consolidated Senior Leverage Ratio" means, as of the last day of
              ----------------------------------
          any fiscal quarter, the ratio of Consolidated Senior Funded Debt on
          such day to Consolidated EBITDA for the period of four consecutive
          fiscal quarters ending as of such day.
<PAGE>
 
             "Senior Subordinated Notes" means those [ __%] Senior Subordinated
              -------------------------
          Notes of the Borrower due 2009, as amended, modified and extended.

             "Subordinated Debt" means (i) the Indebtedness evidenced by the
              -----------------
          Senior Subordinated Notes, and (ii) any other Indebtedness of a member
          of the Consolidated Group which by its terms is expressly subordinated
          in right of payment to the prior payment of the obligations under the
          Credit Agreement and the other Credit Documents on terms and
          conditions satisfactory to the Required Lenders.

     1.2     The pricing grid in the definition of "Applicable Percentage" in
     Section 1.1 of the Credit Agreement is amended to read as follows:

<TABLE>
<CAPTION>
                                                                                
                                                                              Eurodollar        
                                                                              Margin and  
Pricing                                                                     Standby Letter  Trade Letter             
 Level             Consolidated Fixed Charge                  Base Rate        of Credit      of Credit    Commitment
-------                 Coverage Ratio                         Margin            Fee            Fee           Fee
           -----------------------------------------------  --------------   ------------   ------------   ----------
<S>                <C>                                       <C>              <C>           <C>            <C>
I                               less than or equal to 1.75      0.50%           2.00%         0.90%          0.450%
II        greater than 1.75 but less than or equal to 2.00      0.25%           1.75%         0.75%          0.375%
III       greater than 2.00 but less than or equal to 2.50      0.00%           1.50%         0.60%          0.300%
IV        greater than 2.50 but less than or equal to 3.00      0.00%           1.25%         0.45%          0.250%
V         greater than 3.00                                     0.00%           1.00%         0.30%          0.250%
</TABLE>

     1.3 In Section 1.1 of the Credit Agreement, the definitions of "Bridge
     Credit Agreement" and "Bridge Credit Facility" are deleted in their
     entirety.
     
     1.4   Clause (a) of Section 7.9 of the Credit Agreement is amended to read
     as follows: 
                  (a) Consolidated Leverage Ratio. As of the end of each fiscal
                      --------------------------- 
           quarter set forth below, the Consolidated Leverage Ratio shall not be
           greater than the ratio set forth opposite such period:

              The Borrower's first and second fiscal quarter of 1999     4.0:1.0

              The Borrower's third fiscal quarter of 1999 and            3.5:1.0
              each of the Borrower's fiscal quarters thereafter

     1.5   Clause (b) of Section 7.9 of the Credit Agreement is amended to read
     as follows:

                  (b) Consolidated Fixed Charge Coverage Ratio. As of the end of
                      ----------------------------------------
          each fiscal quarter, the Consolidated Fixed Charge Coverage Ratio
          shall not be less than 1.50:1.0.

     1.6   Clause (e) of Section 7.9 of the Credit Agreement is amended to read
     as follows:

                  (e) Capital Expenditures. The aggregate amount of Capital
                      --------------------
           Expenditures for the Consolidated Group will not exceed $75,000,000
           in any fiscal year.

     1.7   A new clause (f) is added to Section 7.9 to read as follows:

                                       2
<PAGE>
 
                        (f) Consolidated Senior Leverage Ratio. As of the end of
                            ----------------------------------
          each fiscal quarter, the Consolidated Senior Leverage Ratio shall not
          be greater than 2.5:1.0.

     1.8   A new clause (c) is added to Section 7.11 to read as follows:

                        (c) Guaranties Given in respect of Other Indebtedness.
                            -------------------------------------------------
          Notwithstanding anything to the contrary contained herein, the
          Borrower will promptly provide, or cause to be provided, to the
          Administrative Agent, a guaranty joinder or guaranty in respect of the
          Loans and obligations hereunder from any Subsidiary or Affiliate of
          the Borrower which shall give a guaranty in respect of the Senior
          Subordinated Notes, together with the other items referenced in
          subsections (a) or (b) hereof, as appropriate.

     1.9  Section 8.1 is amended and restated to read as follows:

          8.1  Indebtedness.
               ------------ 
          Contract, create, incur, assume or permit to exist any Indebtedness,
          except:

                        (a) Indebtedness arising or existing under this Credit
          Agreement and the other Credit Documents;

                        (b) Indebtedness set forth in Schedule 8.1, and
                                                      ------------
          renewals, refinancings and extensions thereof on terms and conditions
          no less favorable than for such existing Indebtedness;

                        (c) purchase money Indebtedness (including Capital Lease
          Obligations and term debt obligations) extended by General Electric
          Capital Corporation or any of its Affiliates in an aggregate
          outstanding principal amount not to exceed $30,000,000 at any time;

                        (d) purchase money Indebtedness (including Capital Lease
          Obligations and mortgage obligations) incurred to provide all or a
          portion of the purchase price or costs of construction of an asset or,
          in the case of a sale/leaseback transaction as described in Section
          8.10, to finance the value of an asset owned by a member of the
          Consolidated Group, provided that (i) such Indebtedness when incurred
                              --------
          shall not exceed the purchase price or cost of construction of such
          asset or, in the case of a sale/leaseback transaction, the fair market
          value of such asset, (ii) no such Indebtedness shall be refinanced for
          a principal amount in excess of the principal balance outstanding
          thereon at the time of such refinancing, and (iii) the total amount of
          all such Indebtedness shall not exceed $20,000,000 at any time
          outstanding;

                        (e) Indebtedness and obligations owing under interest
          rate protection agreements relating to the Obligations hereunder and
          under interest rate, commodities and foreign currency exchange
          protection agreements entered into in the ordinary course of business
          to manage existing or anticipated risks and not for speculative
          purposes;

                        (f) unsecured intercompany Indebtedness owing by a
          member of the Consolidated Group to another member of the Consolidated
          Group (subject, however, to the limitations of Section 8.4 in the case
          of the member of the Consolidated Group extending the intercompany
          loan, advance or credit);

                                       3
<PAGE>
 
                        (g) other senior unsecured Indebtedness of the Borrower
          of up to $5,000,000 in the aggregate at any time outstanding;

                        (h) Support Obligations of Indebtedness permitted under
          this Section 8.1; and

                        (i) Subordinated Debt of the Borrower consisting of

                             (i) the Senior Subordinated Notes in an aggregate
               principal amount of up to $250 million; and

                             (ii) other Subordinated Debt, provided that (A) the
               Borrower shall demonstrate it will be in compliance with the
               financial covenants in Section 7.9 after giving effect thereto on
               a Pro Forma Basis, and (B) no Default or Event of Default shall
               exist after giving effect thereto.

     1.10  Clause (b) of Section 8.8 is amended to read as follows:

                  (b) Make any prepayment, redemption, defeasance or acquisition
          for value of (including without limitation, by way of depositing money
          or securities with the trustee with respect thereto before the due
          date therefor for the purpose of paying when due), or refund,
          refinance or exchange, any Funded Debt (other than intercompany
          Indebtedness permitted hereunder), other than (i) regularly scheduled
          payments of principal and interest on such Funded Debt and (ii) so
          long as no Default or Event of Default would exist after giving effect
          thereto on a Pro Forma Basis, prepayments, redemptions, defeasances
          and acquisitions for value which shall not exceed $5 million in the
          aggregate during the term of this Credit Agreement.

     1.11  In Section 8.11, the reference in clause (iii) of the exception
     to "the Bridge Credit Agreement" is amended to read as "the Senior
     Subordinated Notes" instead.

     1.12  In Section 8.12, the reference in clause (ii) of the exception
     to "the Bridge Credit Agreement" is amended to read as "the Senior
     Subordinated Notes" instead.

     1.13  Clause (j) of Section 9.1(c) is deleted, and clause (k) thereof
     is renumbered as clause (j) thereof.

     2. As required in the definition of "Subordinated Debt," consent is given
hereby to the terms of subordination, and the other terms and conditions, of the
Senior Subordinated Notes as described in Exhibit A attached hereto.
                                          ---------

     3. The Required Lenders hereby waive the requirement under Section
3.4(b)(ii) of the Credit Agreement that the Revolving Commitments be reduced by
an amount equal to fifty percent (50%) of the Net Proceeds received from the
issuance of the Senior Subordinated Notes; provided that, if the Net Proceeds
                                           --------                          
received from the issuance of the Senior Subordinated Notes exceed $225,000,000,
the Revolving Commitments shall be reduced by an amount equal to fifty percent
(50%) of the amount by which the Net Proceeds received from the issuance of the
Senior Subordinated Notes exceed $200,000,000.

                                       4
<PAGE>
 
     4.  The Required Lenders hereby waive any Default or Event of Default
which existed or may have existed prior to the effective date of this Amendment
solely on account of noncompliance with the Consolidated Leverage Ratio under
Section 7.9(a) of the Credit Agreement.

     5.  This Amendment shall be effective upon satisfaction of the
following conditions:

         (a) execution of this Amendment by the Credit Parties and the Required
     Lenders;

         (b) evidence of the issuance of the Senior Subordinated Notes and
     repayment in full of all amounts outstanding under the Bridge Credit
     Facility (and termination of the commitments thereunder);

         (c) receipt by the Administrative Agent of an opinion of counsel to
     the Credit Parties relating to this Amendment, which opinion shall be in
     form and substance satisfactory to the Required Lenders;

         (d) receipt by the Administrative Agent of an officer's certificate
     demonstrating compliance with the financial covenants in Section 7.9 of the
     Credit Agreement after giving effect to the Indebtedness evidenced by the
     Senior Subordinated Notes on a Pro Forma Basis and certifying that no
     Default or Event of Default exists after giving effect thereto; and

         (e) receipt by the Administrative Agent, for the ratable benefit of
     the Lenders which consent to this Amendment (the "Consenting Lenders"), of
                                                       ------------------      
     an amendment fee equal to 7.5 basis points (0.075%) on the aggregate
     Commitments of the Consenting Lenders.

     6.  The Credit Parties hereby affirm (i) the representations and warranties
set out in Section 6 of the Credit Agreement are true and correct as of the date
hereof (except those which expressly relate to an earlier period) and (ii) no
Default or Event of Default presently exists (after giving effect to this
Amendment).

     7. Except as modified hereby, all of the terms and provisions of the Credit
Agreement (including Schedules and Exhibits) shall remain in full force and
effect.

     8.  The Borrower agrees to pay all reasonable costs and expenses of the
Administrative Agent in connection with the preparation, execution and delivery
of this Amendment, including without limitation the reasonable fees and expenses
of Moore & Van Allen, PLLC.

     9.  This Amendment may be executed in any number of counterparts, each of
which when so executed and delivered shall be deemed an original and it shall
not be necessary in making proof of this Amendment to produce or account for
more than one such counterpart.

                                       5
<PAGE>
 
    10.  This Amendment shall be deemed to be a contract made under, and for all
purposes shall be construed in accordance with the laws of the State of North
Carolina.

                  [Remainder of Page Intentionally Left Blank]

                                       6
<PAGE>
 
     IN WITNESS WHEREOF, each of the parties hereto has caused a counterpart of
this Amendment No. 3 to be duly executed and delivered as of the date first
above written.

BORROWER:        JUST FOR FEET, INC.,
--------                           
  a Delaware corporation

                 By:    /s/ Eric L. Tyra
                        ---------------------------
                 Name:  Eric L. Tyra
                 Title: Executive Vice President
                        and Chief Financial Officer

GUARANTORS:      SNEAKER STADIUM, INC.,
----------       a Delaware corporation
                 SNKR HOLDING CORP.,
                 a Delaware corporation
                 ATHLETIC ATTIC MARKETING, INC.,
                 a Florida corporation
                 JUST FOR FEET OF TEXAS, INC.,
                 an Alabama corporation
                 JUST FOR FEET OF NEVADA, INC.,
                 a Nevada corporation
                 JUST FOR FEET SPECIALTY STORES, INC.,
                 a Michigan corporation
 
                 By:    /s/ Eric L. Tyra
                        ---------------------------
                 Name:  Eric L. Tyra
                 Title: Vice President of each
                        of the foregoing Guarantors                     
                 
<PAGE>
 
LENDERS:        NATIONSBANK, N.A.,
-------         individually in its capacity as a           
                Lender and in its capacity as Administrative Agent 
                                                                   
                By: /s/ Nan C. Hillis
                   -----------------------------------             
                Name:  Nan C. Hillis
                     ---------------------------------             
                Title: Sr. Vice President
                      --------------------------------              
  

                SUNTRUST BANK, ATLANTA

                By: /s/ John Frazer
                   -----------------------------------             
                Name: John Frazer                                
                     ---------------------------------             
                Title: Vice President                                  
                      --------------------------------              

                By: /s/ Brian K. Peters
                   -----------------------------------             
                Name: Brian K. Peters                                
                     ---------------------------------             
                Title: Vice President
                      --------------------------------              


                COMPASS BANK

                By: /s/ Janet Brock
                   -----------------------------------             
                Name: Janet Brock                                
                     ---------------------------------             
                Title: Senior Vice President                                  
                      --------------------------------              


                AMSOUTH BANK

                By: /s/ John M. Kettig
                   -----------------------------------             
                Name: John M. Kettig                             
                     ---------------------------------             
                Title: Senior Vice President                               
                      --------------------------------              


                BANCO POPULAR NORTH AMERICA

                By: /s/ Karen Hamilton                       
                   -----------------------------------             
                Name: Karen Hamilton                           
                     ---------------------------------             
                Title: Vice President                               
                      --------------------------------              


                MICHIGAN NATIONAL BANK

                By: /s/ John M. Bebb                              
                   -----------------------------------             
                Name: John M. Bebb                               
                     ---------------------------------             
                Title: Relationship Manager                                 
                      --------------------------------              


                FIRST AMERICAN NATIONAL BANK

                By: /s/ H. Hope Stewart                        
                   -----------------------------------             
                Name: H. Hope Stewart                            
                     ---------------------------------             
                Title: Assistant Vice President                              
                      --------------------------------              

<PAGE>
 
 
                    FIRST UNION NATIONAL BANK

                    By: /s/ Daniel L. Evans
                       -----------------------------
                    Name: Daniel L. Evans
                         ---------------------------
                    Title: Senior Vice President
                          --------------------------

                    MARINE MIDLAND BANK

                    By: /s/ Adriana D. Collins
                       -----------------------------
                    Name: Adriana D. Collins
                         ---------------------------
                    Title: Vice President
                          --------------------------

                    SOUTHTRUST BANK, N.A.

                    By: /s/ William Douglas
                       -----------------------------
                    Name: William Douglas
                         ---------------------------
                    Title: Assistant Vice President
                          --------------------------
 
<PAGE>
 
                                   Exhibit A
                                   ---------
                   Description of Senior Subordinated Notes