<PAGE>

                                                                   Exhibit 10.31

                          THIRD AMENDMENT TO AMENDED
                         AND RESTATED CREDIT AGREEMENT
                         -----------------------------

     This THIRD AMENDMENT TO AMENDED AND RESTATED CREDIT AGREEMENT (this
"Amendment"), dated as of November 10, 2000, is among CELLSTAR CORPORATION, a
 ---------
Delaware corporation (the "Borrower"), each of the banks or other lending
                           --------
institutions which is or may from time to time become a signatory to the
Agreement (hereinafter defined) or any successor or permitted assignee thereof
(each a "Bank" and collectively, the "Banks"), BANK ONE, NA (formerly known as
         ----                         -----
The First National Bank of Chicago), as syndication agent (the "Syndication
                                                                -----------
Agent"), NATIONAL CITY BANK, as documentation agent (the "Documentation Agent"),
-----                                                     -------------------
THE CHASE MANHATTAN BANK (successor by merger to Chase Bank of Texas, National
Association, formerly known as Texas Commerce Bank National Association), a
national banking association ("Chase"), as agent for itself and the other Banks,
                               -----
as issuer of Letters of Credit under the Agreement, and as the swing line lender
(in such capacity, together with its successors in such capacity, the
"Administrative Agent"), as alternate currency agent (in such capacity, together
 --------------------
with its successors in such capacity, the "Alternate Currency Agent").
                                           ------------------------

                                   RECITALS:

     A. The Borrower, the Banks, the Syndication Agent, the Documentation Agent,
the Administrative Agent and the Alternate Currency Agent have entered into that
certain Amended and Restated Credit Agreement dated as of August 2, 1999, as
amended by that certain First Amendment to Amended and Restated Credit Agreement
dated as of November 23, 1999, and as further amended by that certain Second
Amendment to Amended and Restated Credit Agreement dated as of July 12, 2000
(the "Agreement").
      ---------

     B. The Borrower, the Banks, the Syndication Agent, the Documentation Agent,
the Administrative Agent and the Alternate Currency Agent now desire to amend
the Agreement as provided herein.

     NOW, THEREFORE, in consideration of the premises herein contained and other
good and valuable consideration, the receipt and sufficiency of which are hereby
acknowledged, the parties hereto agree as follows:

                                   ARTICLE I

                                  Definitions
                                  -----------

     1.1  Definitions. Capitalized terms used in this Amendment, to the extent
          -----------
not otherwise defined herein, shall have the same meanings as in the Agreement,
as amended hereby.

                                  ARTICLE II

                                  Amendments
                                  ----------

     2.1  Compliance Certificate. Effective as of the date hereof, each
          ----------------------
reference to the date "November 22, 2000" appearing in subsection (d) of Section
                                                       --------------    -------
9.1 of the Agreement is hereby amended to read "December 22, 2000".
---
<PAGE>

                                  ARTICLE III

                             Conditions Precedent
                             --------------------

     3.1  Conditions. The effectiveness of this Amendment is subject to the
          ----------
satisfaction of the following conditions precedent:

          (a) Representations and Warranties. The representations and warranties
              ------------------------------
     contained herein and in all other Loan Documents, as amended hereby, shall
     be true and correct as of the date hereof as if made on the date hereof.

          (b) No Default. No Default shall have occurred and be continuing.
              ----------

          (c) Corporate Matters. All corporate proceedings taken in connection
              -----------------
     with the transactions contemplated by this Amendment and all documents,
     instruments, and other legal matters incident thereto shall be satisfactory
     to the Administrative Agent and its legal counsel, Locke Liddell & Sapp
     LLP.

          (d) Additional Documentation. The Administrative Agent shall have
              ------------------------
     received such additional approvals, opinions, or documents as the
     Administrative Agent or its legal counsel, Locke Liddell & Sapp LLP, may
     reasonably request.

                                  ARTICLE IV

                 Ratifications, Representations and Warranties
                 ---------------------------------------------

     4.1  Ratifications. The terms and provisions set forth in this Amendment
          -------------
shall modify and supersede all inconsistent terms and provisions set forth in
the Agreement and except as expressly modified and superseded by this Amendment,
the terms and provisions of the Agreement and the other Loan Documents are
ratified and confirmed and shall continue in full force and effect. Borrower
agrees that the Agreement, as amended hereby, and the other Loan Documents shall
continue to be legal, valid, binding and enforceable in accordance with their
respective terms.

     4.2  Representations and Warranties. Borrower hereby represents and
          ------------------------------
warrants to the Administrative Agent and the Banks that (1) the execution,
delivery, and performance by the Borrower and the Guarantors of this Amendment
and compliance with the terms and provisions hereof have been duly authorized by
all requisite action on the part of each such Person and do not and will not (a)
violate or conflict with, or result in a breach of, or require any consent under
(i) the articles of incorporation, certificate of incorporation, bylaws,
partnership agreement or other organizational documents of any such Person, (ii)
any applicable law, rule, or regulation or any order, writ, injunction, or
decree of any Governmental Authority or arbitrator, or (iii) any material
agreement or instrument to which any such Person is a party or by which any of
them or any of their property is bound or subject, (2) the representations and
warranties contained in the Agreement, as amended hereby, and any other Loan
Document are true and correct on and as of the date hereof as though made on and
as of the date hereof, and (3) no Default has occurred and is continuing.

                                      -2-
<PAGE>

                                   ARTICLE V

                                 Miscellaneous
                                 -------------

     5.1  Survival of Representations and Warranties. All representations and
          ------------------------------------------
warranties made in this Amendment or any other Loan Document shall survive the
execution and delivery of this Amendment, and no investigation by the
Administrative Agent or any Bank or any closing shall affect the representations
and warranties or the right of the Administrative Agent or any Bank to rely upon
them.

     5.2  Reference to Agreement. Each of the Loan Documents, including the
          ----------------------
Agreement and any and all other agreements, documents, or instruments now or
hereafter executed and delivered pursuant to the terms hereof or pursuant to the
terms of the Agreement as amended hereby, are hereby amended so that any
reference in such Loan Documents to the Agreement shall mean a reference to the
Agreement as amended hereby.

     5.3  Expenses of the Administrative Agent. Borrower agrees to pay on demand
          ------------------------------------
all costs and expenses incurred by the Administrative Agent in connection with
the preparation, negotiation, and execution of this Amendment and any and all
amendments, modifications, and supplements thereto, including without limitation
the costs and fees of the Administrative Agent's legal counsel, and all costs
and expenses incurred by the Administrative Agent in connection with the
enforcement or preservation of any rights under the Agreement, as amended
hereby, or any other Loan Document, including without limitation the costs and
fees of the Administrative Agent's legal counsel.

     5.4  Severability. Any provision of this Amendment held by a court of
          ------------
competent jurisdiction to be invalid or unenforceable shall not impair or
invalidate the remainder of this Amendment and the effect thereof shall be
confined to the provision so held to be invalid or unenforceable.

     5.5  APPLICABLE LAW. NOTWITHSTANDING ANYTHING TO THE CONTRARY CONTAINED IN
          --------------
THE OTHER LOAN DOCUMENTS, THIS AMENDMENT AND ALL OTHER LOAN DOCUMENTS SHALL BE
DEEMED TO HAVE BEEN MADE AND TO BE PERFORMABLE IN DALLAS, DALLAS COUNTY, TEXAS
AND SHALL BE GOVERNED BY AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE
OF TEXAS.

     5.6  Successors and Assigns. This Amendment is binding upon and shall inure
          ----------------------
to the benefit of the Borrower, the Banks, the Syndication Agent, the
Documentation Agent, the Administrative Agent and the Alternate Currency Agent
and their respective successors and assigns, except the Borrower shall not
assign or transfer any of its rights or obligations hereunder without the prior
written consent of the Administrative Agent.

     5.7  Counterparts. This Amendment may be executed in one or more
          ------------
counterparts, each of which when so executed shall be deemed to be an original,
but all of which when taken together shall constitute one and the same
instrument. This Amendment shall not be effective unless and until the Agent,
the requisite Banks, the Borrower and the Guarantors have each executed and
delivered a counterpart hereof; provided, however that execution and delivery by
Holdings shall not be required for effectiveness of this Amendment, but Holdings
shall execute and deliver this Amendment no later than November 30, 2000, and
failure to do so by such date shall constitute an Event of Default under the
Agreement.

                                      -3-
<PAGE>

     5.8   Headings. The headings, captions, and arrangements used in this
           --------
Amendment are for convenience only and shall not affect the interpretation of
this Amendment.

     5.9   Release of Claims. The Borrower and the Guarantors each hereby
           -----------------
acknowledge and agree that none of them has any and there are no defenses,
counterclaims, offsets, cross-complaints, claims or demands of any kind or
nature whatsoever to or against the Administrative Agent, the Alternate Currency
Agent, the Syndication Agent, the Documentation Agent, any of the Banks or the
terms and provisions of or the obligations of the Borrower, any Guarantor or any
Subsidiary created or evidenced by the Agreement or any of the other Loan
Documents, and that neither the Borrower nor any of the Guarantors has any right
to seek affirmative relief or damages of any kind or nature from the
Administrative Agent, the Alternate Currency Agent, the Syndication Agent, the
Documentation Agent or any of the Banks. To the extent any such defenses,
counterclaims, offsets, cross-complaints, claims, demands or rights exist,
Borrower and the Guarantors each hereby waives, and hereby knowingly and
voluntarily releases and forever discharges the Administrative Agent, the
Alternate Currency Agent, the Syndication Agent, the Documentation Agent, each
of the Banks and their respective predecessors, officers, directors, agents,
attorneys, employees, successors and assigns, from all possible claims, demands,
actions, causes of action, defenses, counterclaims, offsets, cross-complaints,
damages, costs, expenses and liabilities whatsoever, whether known or unknown,
such waiver and release being with full knowledge and understanding of the
circumstances and effects of such waiver and release and after having consulted
legal counsel with respect thereto.

     5.10  ENTIRE AGREEMENT. THIS AMENDMENT AND ALL OTHER INSTRUMENTS, DOCUMENTS
           ----------------
AND AGREEMENTS EXECUTED AND DELIVERED IN CONNECTION WITH THIS AMENDMENT EMBODY
THE FINAL, ENTIRE AGREEMENT AMONG THE PARTIES HERETO REGARDING THIS AMENDMENT
AND SUPERSEDE ANY AND ALL PRIOR COMMITMENTS, AGREEMENTS, REPRESENTATIONS AND
UNDERSTANDINGS, WHETHER WRITTEN OR ORAL, RELATING TO THIS AMENDMENT, AND MAY NOT
BE CONTRADICTED OR VARIED BY EVIDENCE OF PRIOR, CONTEMPORANEOUS OR SUBSEQUENT
ORAL AGREEMENTS OR DISCUSSIONS OF THE PARTIES HERETO. THERE ARE NO ORAL
AGREEMENTS AMONG THE PARTIES HERETO.

     Executed as of the date first written above.

                                   BORROWER:
                                   --------

                                   CELLSTAR CORPORATION


                                   By:  /s/ AUSTIN P. YOUNG
                                      -----------------------------------------
                                      Name:  Austin P. Young
                                           ------------------------------------
                                      Title:  Sr. Vice President
                                            -----------------------------------


                                      -4-
<PAGE>

                                   AGENTS AND BANKS:
                                   ----------------


                                   THE CHASE MANHATTAN BANK (successor by merger
                                   to Chase Bank of Texas, National Association,
                                   formerly known as Texas Commerce Bank
                                   National Association), as Administrative
                                   Agent and as a Bank

                                   By: /s/ ALLEN K. KING
                                      -----------------------------------------
                                      Allen K. King
                                      Vice President



                                   BANK ONE, NA (formerly known as The First
                                   National Bank of Chicago), as Syndication
                                   Agent and as a Bank

                                   By:  /s/ TIMOTHY A. SMITH
                                      ------------------------------------------
                                      Name:  Timothy A. Smith
                                           -------------------------------------
                                      Title:  Vice President
                                            ------------------------------------



                                   NATIONAL CITY BANK,
                                   as Documentation Agent and as a Bank


                                   By:  /s/ TOM GURBACH
                                      ------------------------------------------
                                      Name:  Tom Gurbach
                                           -------------------------------------
                                      Title:  Vice President
                                            ------------------------------------



                                   CREDIT LYONNAIS NEW YORK BRANCH


                                   By:  /s/ ATTILA KOC
                                      ------------------------------------------
                                      Name:  Attila Koc
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------

                                      -5-
<PAGE>

                                   WELLS FARGO BANK TEXAS,
                                   NATIONAL ASSOCIATION (formerly known as Wells
                                   Fargo Bank (Texas), National Association)


                                   By:  /s/ BRIAN P. RIORDAN
                                      ------------------------------------------
                                      Name:  Brian P. Riordan
                                           -------------------------------------
                                      Title:  Banking Officer
                                            ------------------------------------


Each of the undersigned Guarantors hereby (a) consents and agrees to this
Amendment, and (b) agrees that its Guaranty shall continue to be the legal,
valid and binding obligation of such Guarantor enforceable against such
Guarantor in accordance with its terms.


                                   NATIONAL AUTO CENTER, INC.


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------


                                   CELLSTAR, LTD.

                                   By:  National Auto Center, Inc.,
                                        General Partner


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------


                                   CELLSTAR FULFILLMENT, LTD.

                                   By:  CellStar Fulfillment, Inc.,
                                        General Partner


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------

                                      -6-
<PAGE>

                                   CELLSTAR FINANCO, INC.


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------



                                   CELLSTAR FULFILLMENT, INC.


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------



                                   NAC HOLDINGS, INC.


                                   By:  /s/ ELAINE FLUD RODRIGUEZ
                                      ------------------------------------------
                                      Elaine Flud Rodriguez
                                      President



                                   CELLSTAR INTERNATIONAL CORPORATION/ASIA


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------



                                   AUDIOMEX EXPORT CORP.


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------

                                      -7-
<PAGE>

                                   CELLSTAR INTERNATIONAL CORPORATION/SA

                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------


                                   CELLSTAR AIR SERVICES, INC.


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------


                                   A & S AIR SERVICE, INC.


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------



                                   CELLSTAR TELECOM, INC.


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------



                                   FLORIDA PROPERTIES, INC.


                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------


                                      -8-
<PAGE>

                                   CELLSTAR GLOBAL SATELLITE SERVICE, LTD.


                                   By:  National Auto Center, Inc.,
                                             General Partner

                                   By:  /s/ AUSTIN P. YOUNG
                                      ------------------------------------------
                                      Name:  Austin P. Young
                                           -------------------------------------
                                      Title:  Sr. Vice President
                                            ------------------------------------

                                      -9-