<PAGE>
 
                                                                   EXHIBIT 10.39

                             CELLSTAR CORPORATION

            AMENDED AND RESTATED ANNUAL INCENTIVE COMPENSATION PLAN

     This Plan amends and restates the CellStar Corporation Annual Incentive
Compensation Plan, which first became effective on December 1, 1994.
Capitalized terms used herein are defined in Article II hereof.

     To the extent permitted under Rule 16b-3, Section 162(m), and any other
applicable law or regulation, the Committee shall have the power, in its sole
discretion, to apply any or all of the amendments effected hereby to outstanding
Awards previously granted under the Plan; provided that, to the extent that the
application of any such amendment to an outstanding Award shall have an Adverse
Consequence for the Company and/or a Participant, such amendment shall not apply
unless it is specifically approved by the Committee and consented to by the
Participant.

     The Plan shall be effective as of March 22, 1996, subject to stockholder
approval of the amendments effected hereby; provided that any Discretionary
Amendment shall not be subject to stockholder approval.


                                   ARTICLE I
                                    PURPOSE
                                    -------

     The purpose of the Plan is to recognize the contributions to the growth,
success, and profitability of the Company and its Subsidiaries provided by key
employees of the Company through the awarding of incentive compensation.  The
Plan is designed to (a) increase the interest of the key employees in the
welfare of the Company and its Subsidiaries; (b) furnish an incentive to such
employees to continue their services for the Company and/or its Subsidiaries;
and (c) provide a means by which the Company and its Subsidiaries may attract
able persons to enter their employ.

     The Plan provides for incentive payments to certain key employees of the
Company and its Subsidiaries based on the achievement of preestablished
Performance Goals.  Incentive Compensation payable pursuant to certain Awards
under the Plan is intended to be deductible by the Company pursuant to the
Section 162(m) Exception.

     With respect to Reporting Participants, the Plan and all transactions under
the Plan are intended to comply with all applicable conditions of Rule 16b-3, to
the extent such Rule is applicable.  To the extent that any provision of the
Plan or action by the Committee fails to so comply, it shall be deemed null and
void ab initio, to the extent permitted by law and deemed advisable by the
Committee.


                                   ARTICLE II
                                  DEFINITIONS
                                  -----------

     For purposes of this Plan, unless the context requires otherwise, the
following terms shall have the meanings indicated:

     "Adverse Consequence" means (i) the loss of qualification of an Award for
special treatment under Rule 16b-3 or the commencement of a new holding period
under such rule; or (ii) the Company's inability to claim the Section 162(m)
Exception with respect to an Award.

     "Annual Incentive Pool" means, with respect to any Fiscal Year, the amount,
if any, equal to the percentage of Earnings for the Fiscal Year in excess of the
Corporate Threshold for the Fiscal Year, as specified in accordance with Section
5.1 below.

     "Award" means the grant by the Committee to an employee of the Company or
its Subsidiaries of the right to receive Incentive Compensation under the Plan.
<PAGE>
 
     "Award Agreement" means a written agreement between a Participant and the
Company that sets out the terms of the grant of an Award.

     "Board" means the Board of Directors of the Company.

     "Cause" includes (a) any act of dishonesty or moral turpitude (including,
without limitation, any act involving a felony or fraud or that ceases or
reasonably may be expected to cause substantial injury to the Company); or (b)
the failure of a Participant to perform his or her duties of employment.  To the
extent that a Participant's Employment Agreement differs from the Plan with
respect to the meaning of "Cause," if such Employment Agreement has been
approved by the Compensation Committee of the Board, the definition included in
such Employment Agreement shall govern.

     "Change of Control" means any of the following:  (i) any consolidation or
merger of the Company in which the Company is not the continuing or surviving
corporation or pursuant to which shares of the Company's Common Stock would be
converted into cash, securities or other property, other than a merger of the
Company in which the holders of the Company's Common Stock immediately prior to
the merger have the same proportionate ownership of Common Stock of the
surviving corporation immediately after the merger; (ii) any sale, lease,
exchange or other transfer (in one transaction or a series of related
transactions) of all or substantially all of the assets of the Company; (iii)
approval by the stockholders of the Company of any plan or proposal for the
liquidation or dissolution of the Company; (iv) the cessation of control (by
virtue of their not constituting a majority of directors) of the Board by the
individuals (the "Continuing Directors") who (x) at the effective date of this
Plan were directors or (y) become directors after the effective date of this
Plan and whose election or nomination for election by the Company's stockholders
was approved by a vote of at least two-thirds of the directors then in office
who were directors at the effective date of this Plan or whose election or
nomination for election was previously so approved); (v) in a Title 11
bankruptcy proceeding, the appointment of a trustee or the conversion of a case
involving the Company to a case under Chapter 7; or (vi) the acquisition of
beneficial ownership (within the meaning of Rule 13d-3 under the Exchange Act)
of an aggregate of 15% or more of the voting power of the Company's outstanding
voting securities by any person or persons acting as a group (within the meaning
of Rule 13d-5 under the Exchange Act) who beneficially owned less than 10% of
the voting power of the Company's outstanding voting securities on the effective
date of this Plan, or the acquisition of beneficial ownership of an additional
5% of the voting power of the Company's outstanding voting securities by any
person or group who beneficially owned at least 10% of the voting power of the
Company's outstanding voting securities on the effective date of this Plan;
provided, however, that, notwithstanding the foregoing, an acquisition shall not
--------  -------                                                               
constitute a Change of Control hereunder if the acquiror is (v) Alan H.
Goldfield ("Goldfield"), (w) a trustee or other fiduciary holding securities
under an employee benefit plan of the Company and acting in such capacity, (x) a
corporation owned, directly or indirectly, by the stockholders of the Company in
substantially the same proportions as their ownership of voting securities of
the Company; (y) a person or group meeting the requirements of clauses (i) and
(ii) of Rule 13d-1(b)(1) under the Exchange Act; or (z) any other person whose
acquisition of shares of voting securities is approved in advance by a majority
of the Continuing Directors; and provided further that no change of control
shall be deemed to have occurred from a transfer of the Company's voting
securities by Goldfield to (v) a member of Goldfield's immediate family (within
the meaning of Rule 16a-1(e) of the Exchange Act) either during Goldfield's
lifetime or by will or the laws of descent and distribution; (w) any trust as to
which Goldfield or a member (or members) of his immediate family is the
beneficiary; (x) any trust as to which Goldfield is the settlor with sole power
to revoke; (y) any entity over which Goldfield has the power, directly or
indirectly, to direct or cause the direction of the management and policies of
the entity, whether through the ownership of voting securities, by contract or
otherwise; or (z) any charitable trust, foundation or corporation under Section
501(c)(3) of the Code that is funded by Goldfield.  To the extent that a
Participant's Employment Agreement differs from the Plan with respect to the
meaning of "Change of Control," if such Employment Agreement has been approved
by the Compensation Committee of the Board of Directors, the definition included
in such Employment Agreement shall govern.

     "Code" means the Internal Revenue Code of 1986, as amended.

     "Committee" means the committee(s) appointed or designated by the Board to
administer the Plan in accordance with Article III.

                                       2
<PAGE>
 
     "Common Stock" means the Common Stock, par value, $.01 per share, of the
Company or, in the event that the outstanding shares of such Common Stock are
hereafter changed into or exchanged for shares of a different stock or security
of the Company or another corporation, such other stock or security.

     "Company" means CellStar Corporation, a Delaware corporation.

     "Corporate Threshold" means, for any Fiscal Year, the minimum level of
Earnings that must be realized by the Company for the Fiscal Year in order to
establish an Annual Incentive Pool for that Fiscal Year, as determined by the
Committee in accordance with Section 5.2 below.

     "Disability" or "Disabled" means that the Participant is qualified for 
long-term disability benefits under the Company's disability plan or insurance
policy; or, if no such plan or policy is then in existence, that the
Participant, because of ill health, physical or mental disability or any other
reason beyond his or her control, is unable to perform his or her duties of
employment for a period of six (6) continuous months, as determined in good
faith by the Committee. To the extent that a Participant's Employment Agreement
differs from the Plan with respect to the meaning of "Disability" or "Disabled,"
if such Employment Agreement has been approved by the Compensation Committee of
the Board of Directors, the definition included in such Employment Agreement
shall govern.

     "Discretionary Amendment" means any amendment to the Plan that does not
require stockholder approval.

     "Earnings" means the earnings of the Company before income taxes and
extraordinary items, but after accrual for the expense of Awards under the Plan.

     "Employment Agreement" means an agreement, if any, between the Company or
any Subsidiary and a Participant, setting forth the terms and conditions of the
Participant's employment by the Company or such Subsidiary.

     "Exchange Act" means the Securities Exchange Act of 1934, as amended.

     "Fair Market Value" of a share of Common Stock means such value as is
determined by the Committee on the basis of such factors as it deems
appropriate; provided that, if the Common Stock is traded on a national
securities exchange or transactions in the Common Stock are quoted on the NASDAQ
National Market System, such value shall be determined by the Committee on the
basis of the last reported sale price for the Common Stock on the date for which
such determination is relevant as reported on the national securities exchange
or the NASDAQ National Market System, as the case may be.  If the Common Stock
is not listed and traded upon a recognized securities exchange or in the NASDAQ
National Market System, the Committee shall make a determination of Fair Market
Value on the basis of the closing bid and asked quotations for such stock on the
date for which such determination is relevant (as reported by a recognized stock
quotation service) or, in the event that there are no bid or asked quotations
for such stock on the date for which such determination is relevant, then on the
basis of the mean between the closing bid and asked quotations on the date
nearest preceding the date for which such determination is relevant for which
such bid and asked quotations were available.  In no event shall "Fair Market
Value" be less than the par value of the Common Stock.

     "Fiscal Year" means the fiscal year of the Company, which is the 12-month
period beginning on each December 1, and ending on the next November 30.

     "Good Reason" means that, without a Participant's written consent, the
Company (a) assigns the Participant duties for which the Participant is not
reasonably equipped by his or her skills and experience, (b) reduces the base
salary of the Participant, (c) requires the Participant to be based anywhere
other than the Company's offices located in the greater Dallas-Fort Worth area,
or (d) terminates benefit or compensation plans or reduces or limits the
Participant's participation therein relative to the participation level of other
employees of similar positions and titles. To the extent that a Participant's
Employment Agreement differs from the Plan with respect to the meaning of "Good
Reason," if such Employment Agreement has been approved by the Compensation
Committee of the Board of Directors, the definition included in such Employment
Agreement shall govern.

                                       3
<PAGE>
 
     "Incentive Compensation" means the amount of performance-based compensation
payable under the Plan for a Fiscal Year to a Participant equal to the
Participant's Allocation for such Participant multiplied by the Annual Incentive
Pool for such Fiscal Year; provided, however, that in no event shall a
Participant's Incentive Compensation for any Fiscal Year exceed $1,000,000.

     "Participant" shall mean a key employee of the Company or a Subsidiary
selected by the Committee to participate in the Plan.

     "Participant's Allocation" means a Participant's allocable percentage of
the Annual Incentive Pool for any Fiscal Year, as determined by the Committee in
accordance with Section 5.6 below.

     "Performance Goals" means the performance measures established by the
Committee for each Participant for any Performance Period in accordance with
Sections 5.2 - 5.4 of the Plan.

     "Plan" means this CellStar Corporation Amended and Restated Annual
Incentive Compensation Plan, as amended from time to time.

     "Reporting Participant" means a Participant who is subject to the reporting
requirements of Section 16 of the Exchange Act.

     "Retirement" means termination of a Participant's employment at or after
the Company's established retirement age, unless otherwise defined in a
particular Award Agreement. To the extent that a Participant's Employment
Agreement differs from the Plan with respect to the meaning of "Retirement," if
such Employment Agreement has been approved by the Compensation Committee of the
Board of Directors, the definition included in such Employment Agreement shall
govern.

     "Rule 16b-3" means Rule 16b-3 promulgated under the Exchange Act, as
amended from time to time.

     "Section 162(m)" means Section 162(m) of the Code and the regulations
promulgated thereunder from time to time.

     "Section 162(m) Exception" means the exception under Section 162(m) for
"qualified performance-based compensation."

     "Stock-Based Compensation" means any Options or shares of Common Stock or
Restricted Stock received by a Participant in lieu of cash compensation pursuant
to the terms of the Company's 1993 Amended and Restated Long-Term Compensation
Plan.

     "Subsidiary" means (i) any corporation in an unbroken chain of corporations
beginning with the Company, if each of the corporations other than the last
corporation in the unbroken chain owns stock possessing a majority of the total
combined voting power of all classes of stock in one of the other corporations
in the chain, (ii) any limited partnership, if the Company or any corporation
described in item (i) above owns a majority of the general partnership interest
and a majority of the limited partnership interests entitled to vote on the
removal and replacement of the general partner, and (iii) any partnership, if
the partners thereof are composed only of the Company, any corporation listed in
item (i) above or any limited partnership listed in item (ii) above.
"Subsidiaries" means more than one of any such corporations, limited
partnerships or partnerships.

     "Target Allocation" means, for a Participant for any Fiscal Year, his or
her maximum percentage share of the Annual Incentive Pool for achievement of his
or her Performance Goals for the Fiscal Year, determined by the Committee in
accordance with Section 5.5 below.

                                       4
<PAGE>
 
                                  ARTICLE III
                                ADMINISTRATION
                                --------------

     3.1  Committee's Authority.  The Plan shall be administered by a committee
          ---------------------                                                
appointed by the Board, consisting of at least two members of the Board;
provided that (i) with respect to any Award that is granted to a Reporting
Participant, such committee shall consist of at least such number of directors
as are required from time to time by Rule 16b-3, and each such committee member
shall qualify as a "disinterested person" under Rule 16b-3; and (ii) with
respect to any Award that is also intended to satisfy the requirements of the
Section 162(m) Exception, such committee shall consist of at least such number
of directors as are required from time to time to satisfy the Section 162(m)
Exception, and each such committee member shall qualify as an "outside director"
within the meaning of Section 162(m).  Any member of the Committee may be
removed at any time, with or without cause, by resolution of the Board, and any
vacancy occurring in the membership of the Committee may be filled by
appointment by the Board. The Committee shall have exclusive authority to (i)
designate the key employees of the Company and its Subsidiaries who shall
participate in the Plan; (ii) establish Performance Goals for each Participant
and certify the extent of their achievement; (iii) establish and certify the
achievement of the Corporate Threshold; (iv) determine each Participant's Target
Allocation; and (v) determine all other terms and conditions of Awards and Award
Agreements under the Plan.

     With respect to restrictions ("mandated restrictions") in the Plan that are
based on the requirements of Rule 16b-3, the Section 162(m) Exception, the rules
of any exchange upon which the Company's securities are listed, or any other
applicable law, rule or restriction (collectively, "applicable law"), to the
extent that any such mandated restrictions are no longer required by applicable
law, the Committee shall have the sole discretion and authority to grant Awards
that are not subject to such mandated restrictions and/or to waive any such
mandated restrictions with respect to outstanding Awards.

     3.2  Committee Action.  A majority of the Committee shall constitute a 
          ----------------  
quorum, and the act of a majority of the members of the Committee present at a
meeting at which a quorum is present shall be the act of the Committee.

     3.3  Committee's Powers.  The Committee shall have the power, in its
          ------------------                                             
discretion, to take such actions as may be necessary to carry out the provisions
and purposes of the Plan and shall have the authority to control and manage the
operation and administration of the Plan.  In order to effectuate the purposes
of the Plan, the Committee shall have the discretionary power and authority to
construe and interpret the Plan, to supply any omissions therein, to reconcile
and correct any errors or inconsistencies, to decide any questions in the
administration and application of the Plan, and to make equitable adjustments
for any mistakes or errors made in the administration of the Plan.  All such
actions or determinations made by the Committee, and the application of rules
and regulations to a particular case or issue by the Committee, in good faith,
shall not be subject to review by anyone, but shall be final, binding and
conclusive on all persons ever interested hereunder.

     In construing the Plan and in exercising its power under provisions
requiring the Committee's approval, the Committee shall attempt to ascertain the
purpose of the provisions in question and when the purpose is known or
reasonably ascertainable, the purpose shall be given effect to the extent
feasible. Likewise, the Committee is authorized to determine all questions with
respect to the individual rights of all Participants under this Plan, including,
but not limited to, all issues with respect to eligibility. The Committee shall
have all powers necessary or appropriate to accomplish its duties under this
Plan including, but not limited to, the power and duty to:

          (a) maintain complete and accurate records of all plan transactions,
     contributions, and distributions. The Committee shall maintain the books of
     accounts, records, and other data in the manner necessary for proper
     administration of the Plan;

          (b) adopt rules of procedure and regulations necessary for the proper
     and efficient administration of the Plan, provided the rules and
     regulations are not inconsistent with the terms of the Plan as set out
     herein. All rules and decisions of the Committee shall be uniformly and
     consistently applied to all Participants in similar circumstances;

          (c) enforce the terms of the Plan and the rules and regulations it
     adopts;

                                       5
<PAGE>
 
          (d) review claims and render decisions on claims for benefits under
     the Plan;

          (e) furnish the Company or the Participants, upon request, with
     information that the Company or the Participants may require for tax or
     other purposes;

          (f) employ agents, attorneys, accountants or other persons (who also
     may be employed by or represent the Company) for such purposes as the
     Committee considers necessary or desirable in connection with its duties
     hereunder; and

          (g) perform any and all other acts necessary or appropriate for the
     proper management and administration of the Plan.


                                  ARTICLE IV
                                  ELIGIBILITY
                                  -----------

     Any key employee of the Company or any of its Subsidiaries whose judgment,
initiative and efforts contribute, or may be expected to contribute, in the
opinion of the Committee, to the successful performance of the Company is
eligible to be selected as a Participant.


                                   ARTICLE V
               DETERMINATION OF GOALS AND INCENTIVE COMPENSATION
               -------------------------------------------------

     5.1  Designation of Annual Incentive Pool. No later than the 90th day of
          ------------------------------------ 
each Fiscal Year, the Committee shall set forth in writing the Committee's
determinations regarding the establishment of an Annual Incentive Pool for such
Fiscal Year.

     5.2  Establishment of Performance Goals. At any time before the 90th day of
          ----------------------------------
each Fiscal Year, the Chairman of the Board may deliver to the Committee his
recommendations for that Fiscal Year regarding designation of Participants and
establishment of Performance Goals for individual Participants. 

     No later than the 90th day of the Fiscal Year, the Committee shall set
forth in writing (i) the key employees designated as Participants for the Fiscal
Year, (ii) the Corporate Threshold for the Fiscal Year, (iii) the individual
Performance Goals established for each Participant, (iv) the Target Allocation
for each Participant, and (v) the Committee's recommendation for the Annual
Incentive Pool. The Corporate Threshold with respect to any Fiscal Year shall
not be less than 105% of the Earnings for the immediately preceding Fiscal Year.

     5.3  Categories of Performance Goals.  The individual Performance Goals
          -------------------------------                                   
established by the Committee for any Fiscal Year may differ among Participants.
For each Participant, his or her individual Performance Goals shall be based on
criteria in one or more of the following categories: (a) performance of the
Company as a whole, performance of a segment of the Company's business, and (c)
individual performance.  In establishing Performance Goals for a Participant,
the Committee shall determine, in its sole discretion, the categories and
criteria to be used in measuring his or her actual performance and the
percentage allocation for each of the criteria (the sum of which shall equal
100%).

     5.4  Performance Criteria for any Fiscal Year.  Performance criteria for 
          ----------------------------------------
the Company shall relate to the achievement of predetermined financial
objectives for the Company and its Subsidiaries on a consolidated basis.
Performance criteria for a segment of the Company's business shall relate to the
achievement of financial and operating objectives of the segment for which the
Participant is accountable. Individual performance criteria shall relate to the
Participant's overall performance, taking into account, among other measures of
performance, the attainment of individual goals and objectives.

                                       6
<PAGE>
 
     5.5  Target Allocation.  No later than the 90th day of the Fiscal Year, the
          -----------------                                                     
Committee shall determine each Participant's Target Allocation for the Fiscal
Year, which shall be his or her base salary for the Fiscal Year as a percent of
the sum of the base salaries of all Participants for the Fiscal Year.

     5.6  Certification.  As soon as practicable after the end of each Fiscal 
          -------------    
Year, the Chairman shall report to the Committee regarding the extent to which
each Participant achieved his or her Performance Goals for the Fiscal Year. As
soon as practicable following verification by the Company's independent public
accountants of the Company's financial results for any Fiscal Year and receipt
of the report of the Chairman of the Board regarding the Participants' actual
performance against the Performance Goal(s) for the Fiscal Year, the Committee
shall certify: (i) whether or not the Company's Earnings exceeded the Corporate
Threshold, (ii) the extent to which each Participant achieved his or her
Performance Goal(s) for the Fiscal Year, and (iii) the calculation of the Annual
Incentive Pool, (iv) the determination by the Committee of the Participant's
Allocation for each Participant and (v) the amount of Incentive Compensation
payable to each Participant under the Plan for the Fiscal Year.

     The Committee shall determine each Participant's Allocation by multiplying
his or her Target Allocation by the percent determined by the Committee to
represent the extent to which such Participant achieved his or her individual
Performance Goals for the Fiscal Year. The Committee shall then determine each
Participant's Incentive Compensation by multiplying his or her Participant's
Allocation by the amount in the Annual Incentive Pool; provided that, in no
event shall a Participant's Incentive Compensation during any Fiscal Year exceed
$1,000,000. Further, after the Committee has determined a Participant's
Allocation, the Committee, in its discretion, may reduce any such Participant's
Allocation pursuant to Section 5.7 below.

     5.7  Committee Discretion.  The Committee may, in its discretion, reduce or
          --------------------                                                  
eliminate a Participant's Target Allocation based upon such objective or
subjective criteria as it deems appropriate or to take into account
circumstances that could not have been anticipated when it established the
Performance Goals.

     The Committee shall have the sole discretion and authority to change any
Participant's Performance Goals or criteria for any Fiscal Year to the extent it
deems such changes advisable in light of extraordinary circumstances not
foreseen at the time of grant of an Award; provided that, the Committee may not
retroactively change Performance Goal(s) or criteria relating to any Award
intended to satisfy the Section 162(m) Exception, except (i) in the event of
changes in accounting practices or, (ii) to the extent consistent with Code
Section 162(m) and its regulations, circumstances that could not have been
anticipated when it established such Performance Goals and criteria.

     5.8  Nonallocation. The Committee shall not be obligated to apply the
          ------------- 
entire Annual Incentive Pool for any Fiscal Year to Participants' Incentive
Compensation. Any amount not so applied for a Fiscal Year shall lapse and remain
part of the general assets of the Company; no portion of any such amount shall
be carried over to an Annual Incentive Pool for any subsequent Fiscal Year.


                                  ARTICLE VI
                       PAYMENT OF INCENTIVE COMPENSATION
                       ---------------------------------

     6.1  Form and Time of Payment. Subject to any forfeiture provisions set
          ------------------------
forth in the Plan or in any Award Agreement, a Participant's Incentive
Compensation for each Fiscal Year shall be paid in a cash lump sum as soon as
practicable following certification by the Committee in accordance with Section
5.4 above, unless the Participant has elected to defer receipt of all or a
portion of the Participant's Incentive Compensation in accordance with Section
6.2 below; provided that, in the sole discretion of the Committee, such payment
may be made in the form of Common Stock, nonqualified stock options, or
restricted stock granted under, and in accordance with, the terms of the
Company's 1993 Amended and Restated Long-Term Incentive Compensation Plan. Any
Stock-Based Compensation that is payed in lieu of cash shall be of an equivalent
value to the foregone cash compensation (taking into account, among other
factors, the term of an option and its exercise price, any vesting requirements
with respect to options or shares of Restricted Stock, transferability rights
and all other relevant factors), as verified by the Company's independent public
accountants (and in accordance with the Black Scholes method of valuation when
applicable). The exercise price for any options granted in lieu of cash
Incentive Compensati on awarded hereunder shall be no less than

                                       7
<PAGE>
 
the Fair Market Value per share of the Company's Common Stock on the date of
certification by the Compensation Committee of such Incentive Compensation.

     6.2  Participant Deferrals.
          --------------------- 

                  (a) General. For each Fiscal Year, a Participant may elect,
          prior to the first day of such Fiscal Year (in accordance with
          procedures and rules established by the Committee), to defer receipt
          of, and contribute to his or her Deferred Account (herein so called)
          established under this Plan, any part or all of his Incentive
          Compensation. Each election made under this Section 6.2(a) shall be
          made in writing on a form prescribed by and filed with the Committee,
          and shall be irrevocable for the Fiscal Year for which it is made.

                  (b) Deferred Accounts. The Company shall establish and
          maintain on its books a Deferred Account for each Participant who
          elects to defer the receipt of any amount pursuant to this Section
          6.2(b). Such Deferred Account shall be designated by the name of the
          Participant for whom it is established and the Fiscal Year to which it
          relates. The amount attributable to any Incentive Compensation elected
          to be deferred shall be credited to such Deferred Account. A
          Participant shall have a separate Deferred Account for each Fiscal
          Year for which he makes such an election. Each Deferred Account shall
          reflect the credits and charges allocable thereto in accordance with
          the Plan. The Committee shall maintain, or cause to be maintained,
          records which will adequately disclose at all times the state of each
          separate Deferred Account hereunder. The books, forms and methods of
          accounting shall be entirely subject to the supervision of the
          Committee.

                  (c) Investment of Deferred Accounts. Each Deferred Account
          shall accrue interest from the date the Deferred Account is
          established until the date it is paid under Section 6.2(e) below, at a
          rate which is equal to the Company's cost of funds on the date the
          Incentive Compensation is certified by the Committee.

                  (d) Time of Payment. A Participant shall be entitled to
          receive the entire amount in his or her Deferred Account upon the
          earliest to occur of (i) the January 2 designated by the Participant
          on his or her deferral election, which shall be at least two (2) years
          but no more than ten (10) years after the end of the Fiscal Year to
          which such Deferred Account relates, (ii) termination of employment
          for any reason, including death, or (iii) termination of the Plan.
          Such payment shall begin within 60 days after the date which causes
          payment to become due.

                  (e) Form of Payment. A Participant's Deferred Account shall be
          paid in one cash payment. The Committee shall value such Deferred
          Account as of the date which causes payment to become due.

                  (f) Amounts Nonforfeitable. When payment of all or a portion
          of a Participant's Incentive Compensation is deferred, the amount
          deferred is nonforfeitable. Deferred Accounts are unfunded and
          constitute general obligations of the Company.


                                  ARTICLE VII
               TERMINATION OF EMPLOYMENT PRIOR TO CERTIFICATION
               ------------------------------------------------

     7.1 Pro Rata Payment for Certain Terminations. Unless otherwise permitted
         -----------------------------------------
by the Committee in its sole discretion, if a Participant's employment with the
Company and all of its Subsidiaries terminates before the end of a Fiscal Year
for one of the reasons set forth in this Section 7.1, the Committee shall
calculate such Participant's Incentive Compensation as if he or she remained
employed for the entire Fiscal Year, and such Participant shall be entitled to
receive a pro rate portion of such Incentive Compensation based on the portion
of the Fiscal Year such Participant was employed by the Company or a Subsidiary.
The reasons for termination subject to this Section 7.1 are (i) within one year
following a Change of Control, the Company terminates a Participant's employment
for any reason (or for nor reason), (ii) the Company terminates a Participant's
employment other than for Cause, (iii) a

                                       8
<PAGE>
 
Participant voluntarily terminates employment with Good Reason, (iv) the
Retirement of the Participant, (v) the Participant dies, or (vi) the Participant
becomes Disabled.

     7.2  Forfeiture Upon Other Terminations. If, prior to the end of a Fiscal
          ----------------------------------
Year, a Participant's employment with the Company and all of its Subsidiaries
terminates for any reason other than those described in Section 7.1 above, the
Participant will immediately forfeit any right to receive any Incentive
Compensation hereunder for such Fiscal Year.

                                  ARTICLE VIII
                              DEATH OR DISABILITY
                              -------------------

     8.1  Payment to Beneficiary.  Each Participant shall designate, in a manner
          ----------------------                                                
prescribed by the Committee, a beneficiary to receive payments due under the
Plan in the event of his or her death.  If a Participant dies prior to the date
of payment of his or her Incentive Compensation for a Fiscal Year, such
Incentive Compensation shall be paid to the Participant's named beneficiary, or
if no properly designated beneficiary survives the Participant, such
Participant's Incentive Compensation shall be paid to the Participant's estate
or personal representative.

     8.2  Disability.  If a guardian or conservator has been appointed for a
          ----------                                                        
Disabled Participant, the Committee shall pay the Participant's Incentive
Compensation to such guardian or conservator.


                                  ARTICLE XIII
                            MISCELLANEOUS PROVISIONS
                            ------------------------

     9.1  Effect of the Plan. Neither the adoption of this Plan nor any action
          ------------------
of the Board or the Committee shall be deemed to give any person any right to be
granted an Award or any other rights except as may be evidenced by an Award
Agreement, or any amendment thereto, duly authorized by the Committee and
executed on behalf of the Company, and then only to the extent and upon the
terms and conditions expressly set forth therein.

     9.2  Non-Assignability.  A Participant may not alienate, assign, pledge,
          -----------------                                                  
encumber, transfer, sell or otherwise dispose of any rights or benefits awarded
hereunder prior to the actual receipt thereof; and any attempt to alienate,
assign, pledge, sell, transfer or assign prior to such receipt, or any levy,
attachment, execution or similar process upon any such rights or benefits shall
be null and void.

     9.3  No Right Continue in Employment.  Nothing in the Plan confers upon any
          -------------------------------                                       
employee the right to continue in the employ of the Company or any Subsidiary,
or interferes with or restricts in any way the right of the Company and its
Subsidiaries to discharge any employee at any time (subject to any contract
rights of such employee).

     9.4  Indemnification of Committee.  No member of the Committee, nor any
          ----------------------------                                      
officer or employee of the Company acting on behalf of the Committee, shall be
personally liable for any action, determination, or interpretation taken or made
in good faith with respect to the Plan, and all members of the Committee, and
each officer or employee of the Company acting on its behalf shall, to the
extent permitted by law, be fully indemnified and protected by the Company with
respect to any such action, determination or interpretation.

     9.5   No Plan Funding. The Plan shall at all times be entirely unfunded and
           ---------------
no provision shall at any time be made with respect to segregating assets of the
Company for payment of any amounts hereunder. No Participant, beneficiary, or
other person shall have any interest in any particular assets of the Company by
reason of the right to receive incentive compensation under the Plan.
Participants and beneficiaries shall have only the rights of a general unsecured
creditor of the Company.

     9.6   Governing Law.  This Plan shall be construed in accordance with the
           -------------
laws of the State of Texas and the rights and obligations created hereby shall
be governed by the laws of the State of Texas.

                                       9
<PAGE>
 
     9.7  Amendment or Discontinuance. The Plan may be amended or discontinued
          ---------------------------
by the Committee, without the approval of the stockholders; provided that no
amendment shall be made without approval of the stockholders of the Company if
such approval is required under the Code, Rule 16b-3, the requirements of any
exchange upon which the Company's securities are listed, or any other applicable
law. In addition, no termination or amendment of the Plan may, without the
consent of the Participant to whom any Award has theretofore been granted,
adversely affect the rights of such Participant with respect to such Award.

     9.8  Binding Effect.  This Plan shall be binding upon and inure to the
          --------------
benefit of the Company, its successors and assigns, and the Participants, and
their heirs assigns and personal representatives.

     9.9  Construction of Plan.  The captions used in this Plan are for the
          -------------------- 
convenience only and shall not be construed in interpreting the Plan. Whenever
the context so requires, the masculine shall include the feminine and neuter,
and the singular shall also include the plural, and conversely.

     9.12 Integrated Plan.  This Plan constitutes the final and complete
          ---------------
expression of agreement among the parties hereto with respect to the subject
matter hereof.



     IN WITNESS WHEREOF, the Company has caused this instrument to be executed
as of March 22, 1996, by its President and Secretary pursuant to prior action
taken by the Board.

 
                               CELLSTAR CORPORATION


 
                               By: /s/ Terry S. Parker
                                  --------------------
                                  President

Attest:


/s/ Elaine Flud Rodriguez
-------------------------
Secretary

                                       10