<PAGE>   1
                                                                  EXHIBIT 10.29

                          REGISTRATION RIGHTS AGREEMENT

      THIS AGREEMENT (this "Registration Rights Agreement") is entered into as
of the 3rd day of June, 1998 between Costilla Energy, Inc., a Delaware
corporation (the "Company"), Enron Capital & Trade Resources Corp., a Delaware
corporation and Joint Energy Development Investments II Limited Partnership
(collectively, the "Purchasers").

                              W I T N E S S E T H:

      WHEREAS, the Company and Purchasers have entered into that certain
Securities Purchase Agreement (the "Agreement") dated as of June 3, 1998,
whereby Purchasers have agreed, for the consideration set forth therein, to
purchase an aggregate of 50,000 shares (the "Shares") of Series A Preferred
Stock, $0.10 par value per share (the "Preferred Stock"), of the Company; and

      WHEREAS, in order to induce Purchasers to enter into the Agreement, the
Company has agreed to enter into this Registration Rights Agreement and to grant
the Rights (as hereinafter defined) to Purchasers contained herein;

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

                                   SECTION 1.
                         CERTAIN DEFINITIONS AND TERMS.

      The following terms have the meanings indicated:

      "Affiliate" shall have the meaning given to such term in Rule 405 under 
the Securities Act.

      "Commission" means the Securities and Exchange Commission or any successor
thereof.

      "Common Stock" means the common stock, $0.10 par value per share, of the
Company.

      "Controlling Person" has the meaning ascribed thereto in Section 4(a) of
this Registration Rights Agreement.

      "Exchange Act" means the Securities Exchange Act of 1934, as amended, and
the rules and regulations promulgated thereunder.

      "Existing Registration Rights Agreement" means article IV of that certain
Consolidation Agreement dated as of September 13, 1996, as amended October 8,
1996, by and among the 

<PAGE>   2

Company, Costilla Energy, L.L.C., CSL Management Corporation, Valley Gathering
Company, Cadell S. Liedtke, Michael J. Grella, Henry G. Musselman and
NationsBanc Capital Corporation.

      "Existing Rights Holder" shall have the meaning ascribed thereto in
Section 2(a)(vii) of this Registration Rights Agreement.

      "Form S-3" means Form S-3 as promulgated by the Commission on the date
hereof or any successor form or method of registration that provides for the
incorporation by reference of historical information regarding the Company's
business and financial affairs and permits registration of resales of
Registrable Securities for a continuous and indefinite period of time of no less
than two years pursuant to such form or method of registration.

      "Holder" means Purchasers and any other Person holding Registrable
Securities; provided, that such Person acquired such Registrable Securities in
accordance with Section 7 of this Registration Rights Agreement.

      "Indemnitee" has the meaning ascribed thereto in Section 4(d) of this
Registration Rights Agreement.

      "Indemnitor" has the meaning ascribed thereto in Section 4(d) of this
Registration Rights Agreement.

      "Initiating Seller" has the meaning ascribed thereto in Section 2(b)(iii)
of this Registration Rights Agreement.

      "Majority" shall mean more than 50.00%.

      "NBCC" shall mean NationsBanc Capital Corporation.

      "Person" means any individual, firm, corporation, trust, association,
partnership, limited partnership, limited liability company, joint venture or
other entity.

      "Registrable Securities" means all shares of Common Stock of the Company
issued or issuable to a Holder upon conversion of the Shares or any Common Stock
or other securities issued or issuable as a dividend or other distribution upon
or with respect to such Shares or such Common Stock.

      "Register", "registered" and "registration" refer to a registration
effected by preparing and filing a registration statement in compliance with the
Securities Act and the declaration or ordering of effectiveness of such
registration statement.

      "Rights" means all rights, remedies, powers, benefits, and privileges
granted to the Holders pursuant to this Registration Rights Agreement.


                                      A - 2

<PAGE>   3




      "Rule 415" means Rule 415 under the Securities Act as promulgated by the
Commission on the date hereof or any successor rule or method of registration
that permits the registration of resales of Registrable Securities for a
continuous and indefinite period of time of no less than two years pursuant to
such rule or method of registration.

      "Securities Act" means the Securities Act of 1933, as amended, and the
rules and regulations promulgated thereunder.

                                   SECTION 2.
                              REGISTRATION RIGHTS.


      (a)    DEMAND REGISTRATION RIGHTS. (i) On any date after the date of I the
earlier of (A) the mailing by any Holder of a notice of conversion of Shares for
Registrable Securities or (B) the issuance of Registrable Securities, any Holder
or Holders possessing in the aggregate a Majority of the Registrable Securities
shall have the right to request, in writing specifying that such request is made
pursuant to this Section 2(a), that the Company file a registration statement
under the Securities Act covering not less than 250,000 Registrable Securities
(unless fewer Registrable Securities are held by the Holders, in which case,
covering all such Registrable Securities). Such request shall set forth the
proposed plan of distribution for the Registrable Securities to be registered.
Within five days of such request, the Company shall give written notice of such
request to all other Holders of Registrable Securities and shall include in the
registration in respect of which notice has been given all Registrable
Securities with respect to which the Company has received written requests from
Holders for inclusion therein within ten days after the Company's notice
regarding such registration has been given as provided in Section 11(a) of this
Registration Rights Agreement. Within 45 days of such request, or, in the event
that Form S-3 under the Securities Act is available to the Company to effect
such registration, within 30 days of such request, the Company shall file a
registration statement to register under the Securities Act all Registrable
Securities subject to such request; provided, however, that the Company may
defer its obligations under this Section 2(a) for a period of no more than 30
days (which 30 days shall be in addition to the 45-day or 30-day period, as
applicable, permitted above) if the Company obtains written advice from the
Company's outside securities counsel (which counsel shall be a nationally
recognized securities law firm or a law firm acceptable to the Holders) that
filing such a registration statement would require public disclosure by the
Company of any material non-public development; provided, further, that if such
written advice is received by the Company, the request for registration may be
withdrawn by the Holder who requested such registration (and shall not be
treated as a registration hereunder for any purpose); and provided further, that
if such request for registration has not been withdrawn, once such information
has been publicly disclosed by the Company, the Company shall promptly proceed
to fulfill its obligations under this Section 2(a).

                  (ii) Notwithstanding the foregoing, in the event the Company 
reasonably expects to file, within 60 days of a request made pursuant to this 
Section 2(a), a registration statement pertaining to securities for the account
of the Company (except a registration statement on Form S-4


                                      A - 3

<PAGE>   4




or Form S-8 or with respect to a transaction subject to Rule 145 under the
Securities Act) then such request shall constitute a request made pursuant to
Section 2(b) hereof to include in such registration statement all Registrable
Securities subject to such request and the Company shall not be obligated to
file a separate registration statement for the Registrable Securities subject to
such request; provided that the Company is actively employing in good faith all
reasonable efforts to cause such registration statement to become effective and
that the Company's estimate of the date of filing of such registration statement
is made in good faith.

                  (iii) Except as provided in Section 2(a)(iv), the Company
shall be obligated to effect only three registrations in the aggregate pursuant
to this Section 2(a) with respect to all Holders (including Purchasers and all
of their direct and indirect transferees pursuant to Section 7 hereof);
provided, however, that a registration requested pursuant to this Section 2(a)
shall not be deemed to be a "registration" for purposes of any provision of this
Section 2(a), (A) if a registration statement with respect thereto has not been
declared effective by the Commission, (B) if after such registration statement
has become effective, such registration is interfered with by any stop order,
injunction or other order or requirement of the Commission or other governmental
agency or court for any reason not the fault of a holder of Registrable
Securities and all of the Registrable Securities covered thereby have not been
sold, (C) if the conditions to closing specified in the selling agreement or
underwriting agreement entered into in connection with such registration are not
satisfied or waived by the parties thereto other than a holder of Registrable
Securities, or (D) if the Holders of Registrable Securities are not able to
register and sell all of the Registrable Securities requested to be included in
such registration by Holders entitled to registration rights pursuant to this
Registration Rights Agreement.

                  (iv) At any time the Company is eligible to register
Registrable Securities for resale for a continuous and indefinite period of time
of not less than two years on Form S-3 pursuant to Rule 415 or otherwise, at the
election of Holders holding a Majority of the Registrable Securities, the number
of registrations the Company shall be obligated to effect pursuant to this
Section 2(a) shall be reduced to one, if within 30 days of receipt by the
Company of notice from such Holders of such election, the Company files a
registration statement to register under the Securities Act all Registrable
Securities for continuous and indefinite resale for a period of not less than
two years, and such registration is declared effective by the Commission and
remains continuously effective for the lesser of (A) two years from the
effective date of such registration, or (B) the date after which all Registrable
Securities have been sold by the Holders thereof.

                  (v) Distribution by the Holder or Holders of the Registrable
Securities registered pursuant to this Section 2(a) may be made in any lawful
manner, including underwritten public offerings and non-underwritten "at the
market" distributions. If any such offering is to be an underwritten public
offering, the Holder or Holders of a Majority of such Registrable Securities
shall have the right to select the managing underwriter or underwriters, subject
to the approval of the Company, which approval shall not be unreasonably
withheld.



                                      A - 4

<PAGE>   5




                  (vi) The Holders shall not make a request to the Company to
effect any registration pursuant to this Section 2(a) during the 180-day period
beginning on the effective date of the first registration of Registrable
Securities made pursuant to this Section 2(a) or during the 90-day period
beginning on the effective date of any registration statement relating to any
registration of Registrable Securities made pursuant to Section 2(b) of this
Registration Rights Agreement.

                  (vii) (A) Whenever the Company shall effect a registration
pursuant to this Section 2(a), (1) the Company may include securities of the
Company in such registration for sale for its own account, and (2) any Person
other than a Holder who is entitled to a piggy-back registration rights under
the Existing Registration Rights Agreement with respect to a registration
statement filed to effect a registration under this Section 2(a) ("Existing
Rights Holders") may include securities of the Company with respect to which
such rights apply in such registration for sale, in each case in accordance with
the method of disposition specified by the Holders requesting registration of
Registrable Securities unless (if the method of disposition shall be an
underwritten public offering) the lead managing underwriter advises the Holders
that market factors would materially reduce the price received by the Holders if
the securities held by such Existing Rights Holders and the Company are included
therein or would reduce the number of Registrable Securities that could be sold
by Holders participating in such registration if the securities of such Existing
Rights Holders and the Company are included therein.

                        (B) If the lead managing underwriter for the offering
advises that marketing factors require the inclusion in such registration of 
some or all of the Registrable Securities sought to be registered by the Company
or such Existing Rights Holders to be limited or that the number of securities
to be registered at the insistence of the Company and any Existing Rights 
Holders plus the number of Registrable Securities sought to be registered by the
Holders should be limited due to marketing factors, the number of Registrable 
Securities sought to be registered by the Company and such Existing Rights 
Holders shall be reduced as follows: (1) the number of securities to be 
registered by the Company shall first be reduced, to the number recommended by 
the managing underwriter; (2) if, after all securities sought to be registered 
by the Company have been eliminated, the managing underwriter still recommends a
reduction in the number of securities to be offered, the number of securities 
sought to be registered by Existing Rights Holders shall be reduced, pro rata,
based on the number of securities sought to be registered by each such Holder, 
to the number recommended by the managing underwriter; and in no event shall the
number of securities offered by the Holders be reduced.

                  (viii) The Company agrees (A) not to effect any public sale or
distribution of its equity securities (other than pursuant to Form S-4, Form S-8
or any successor form thereto and, in the case of any registration under Section
2(b), equity securities being sold for the account of the Company in any
registration which includes Registrable Securities of Holders) during the 14-day
period prior to, and during the 90-day period beginning on, the effective date
of a registration statement filed pursuant to Section 2(a) or 2(b), and (B) to
cause each holder of its privately placed equity securities possessing
registration rights purchased from the Company at any time on or after the date
of this Registration Rights Agreement to agree not to effect any public sale or
distribution


                                      A - 5

<PAGE>   6




(including sales pursuant to Rule 144 under the Securities Act) of any such
securities during such period.

      (b) PIGGYBACK REGISTRATION RIGHTS. (i) If the Company at any time proposes
to register any of its Common Stock under the Securities Act (other than
registrations on Forms S-4 or S-8 or any successor forms thereto or
registrations of securities in connection with a Rule 145 transaction), whether
of its own accord or at the request of any holder or holders of its securities,
it shall each such time promptly give written notice to all Holders of its
intention to do so.

                  (ii) Upon the written request of a Holder or Holders delivered
to the Company within 10 business days after receipt of any such notice, the
Company shall use its best efforts (subject to the provisions of this Section
2(b)) to cause all Registrable Securities, the Holders of which shall have so
requested registration thereof, to be registered under the Securities Act, all
to the extent requisite to permit the sale or other disposition by the Holder or
Holders of all of such Registrable Securities; provided, however, the Company
may elect not to file a registration statement pursuant to this Section 2(b) or
may withdraw any registration statement filed pursuant to this Section 2(b) at
any time prior to the effective date thereof.

                  (iii) If the lead managing underwriter for the respective
offering advises that marketing factors require the exclusion from such
registration of some or all of the Registrable Securities sought to be
registered by the Holders or that the total number of securities to be
registered at the insistence of the Company and any other selling shareholders
plus the number of Registrable Securities sought to be registered by the Holders
should be limited due to marketing factors, the number of Registrable Securities
and other securities sought to be registered by each Holder, the Company and
such other selling shareholders shall be reduced as follows:

                        (A) if the offering is an offering of securities for the
account of the Company, (1) the number of securities to be registered by selling
Persons other than the Company, NBCC, Purchasers and other Holders shall first 
be reduced, prorata, based on the number of securities sought to be registered 
by each such other selling Person, to the number recommended by the lead 
managing underwriter; (2) if, after all securities sought to be registered by 
selling Persons other than the Company, NBCC, Purchasers and other Holders have 
been eliminated, the lead managing underwriter still recommends a reduction in 
the number of securities to be offered, the number of Registrable Securities 
sought to be registered by Holders other than the Purchasers shall be reduced,
prorata, based on the number of Registrable Securities sought to be registered
by each such Holder, to the number recommended by the managing underwriter; (3)
if, after all Registrable Securities sought to be registered by such other
Holders have been eliminated, the lead managing underwriter still recommends a 
reduction in the number of securities to be offered, the number of Registrable 
Securities sought to be registered by the Purchasers shall be reduced, pro rata,
based on the number of Registrable Securities sought to be registered by each 
such Purchaser, to the number recommended by the lead managing underwriter, and 
(4) if, after all Registrable Securities sought to be registered by Purchasers 
have been eliminated, the lead managing underwriter still recommends a reduction
in the number of securities to be offered, the number of Registrable Securities
sought to


                                      A - 6

<PAGE>   7




be registered by NBCC shall be reduced, pro rata, based on the number of
Registrable Securities sought to be registered by NBCC, to the number
recommended by the lead managing underwriter; and in no event shall the number
of securities offered by the Company be reduced;

                         (B) if the offering is an offering of securities
initiated for the benefit of an Existing Rights Holder other than NBCC, then (1)
up to 50% of the total amount of securities recommended by the lead managing
underwriter to be registered shall be reserved for securities owned, and
requested to be registered, by NBCC and the remainder shall be allocated among
Existing Rights Holders other than NBCC, the Company, Purchasers, Holders and
other selling Persons; (2) the number of securities to be registered by the
Company, Existing Rights Holders other than NBCC, Purchasers, Holders and such
other selling Persons shall first be reduced, pro rata, based on the number of
securities sought to be registered by the Company and each such other selling
Person, to the number recommended by the lead managing underwriter; (3) if,
after all securities sought to be registered by the Company and such other
selling Persons have been eliminated, the lead managing underwriter still
recommends a reduction in the number of securities to be offered, the number of
Registrable Securities sought to be registered by Holders other than the
Purchasers shall be reduced, pro rata, based on the number of Registrable
Securities sought to be registered by each such Holder, to the number
recommended by the lead managing underwriter; (4) if, after all Registrable
Securities sought to be registered by such other Holders have been eliminated,
the lead managing underwriter still recommends a reduction in the number of
securities to be offered, the number of Registrable Securities sought to be
registered by the Purchasers shall be reduced, pro rata, based on the number of
Registrable Securities sought to be registered by each such Purchaser, to the
number recommended by the lead managing underwriter; and (5) if, after all
Registrable Securities sought to be registered by Purchasers have been
eliminated, the lead managing underwriter still recommends a reduction in the
number of securities to be offered, the number of securities sought to be
registered by the Existing Rights Holders other than NBCC shall be reduced, pro
rata, based on the number of securities sought to be registered by each such
Existing Rights Holder other than NBCC, to the number recommended by the lead
managing underwriter; and

                         (C) if the offering is an offering of securities
initiated for the benefit of selling shareholders other than Holders and other
than as described under (B) above, (1) the number of securities to be registered
by selling Persons (including the Company) other than the selling shareholder(s)
who initiated the registration (the "Initiating Seller") and Holders shall first
be reduced, pro rata, based on the number of securities sought to be registered
by each such other selling Person, to the number recommended by the lead
managing underwriter, (2) if, after all securities sought to be registered by
selling Persons other than the Initiating Seller and Holders have been
eliminated, the lead managing underwriter still recommends a reduction in the
number of securities to be offered, the number of Registrable Securities sought
to be registered by Holders other than the Purchasers shall be reduced, pro
rata, based on the number of Registrable Securities sought to be registered by
each such Holder, to the number recommended by the lead managing underwriter;
and (iii) if, after all securities sought to be registered by selling Persons
other than the Initiating Seller and the Purchasers have been eliminated, the
lead managing underwriter still recommends a reduction in the number of
securities to be offered, the number of Registrable Securities sought to


                                      A - 7

<PAGE>   8




be registered by the Purchasers shall be reduced, pro rata, based on the number
of Registrable Securities sought to be registered by each such Purchaser, to the
number recommended by the lead managing underwriter.

       (c)        REGISTRATION PROCEDURES. If and whenever the Company is 
required by the provisions of this Section 2 to effect the registration of any 
Registrable Securities under the Securities Act, the Company shall, as 
expeditiously as possible,

                  (i) cooperate with any underwriters for, and the Holders of,
such Registrable Securities, and shall enter into a usual and customary
underwriting agreement with respect thereto and take all such other reasonable
actions as are necessary or advisable to permit, expedite and facilitate the
disposition of such Registrable Securities in the manner contemplated by the
related registration statement, including without limitation, the inclusion in
such registration statement of any information relating to the Company or its
subsidiaries which such Holders or underwriters deem reasonably necessary to
facilitate such disposition, in each case to the same extent as if all the
securities then being offered were for the account of the Company, and the
Company shall provide to any Holder of such Registrable Securities, any
underwriter participating in any distribution thereof pursuant to a registration
statement, and any attorney, accountant or other agent retained by any Holder or
underwriter, reasonable access to appropriate Company officers and employees to
answer questions and to supply information reasonably requested by any such
Holder, underwriter, attorney, accountant or agent in connection with such
registration statement; provided, however, that each such party shall be
required to maintain in confidence and not to disclose to any other person any
information or records reasonably designated by the Company in writing as being
confidential, until such time as (A) such information becomes a matter of public
record (whether by virtue of its inclusion in such registration statement or
otherwise), or (B) such person shall be required so to disclose such information
pursuant to the subpoena or order of any court or other governmental agency or
body having jurisdiction over the matter (subject to the requirements of such
order, and only after such person shall have given the Company prompt prior
written notice of such requirement), or (C) such information is required to be
set forth in such registration statement or the prospectus included therein or
in an amendment to such registration statement or an amendment or supplement to
such prospectus in order that such registration statement, prospectus, amendment
or supplement, as the case may be, does not contain an untrue statement of a
material fact or omit to state therein a material fact required to be stated
therein or necessary to make the statements therein not misleading in light of
the circumstances then existing;

                  (ii) furnish or cause to be furnished to each Holder of the
Registrable Securities covered by such registration statement, on the date that
such Registrable Securities are to be delivered to the underwriters for sale
pursuant to such registration or, if such Registrable Securities are not being
sold through underwriters, on the date the registration statement with respect
to such Registrable Securities becomes effective (A) an opinion, dated such
date, of the outside counsel representing the Company for the purposes of such
registration, addressed to the underwriters, if any, and to the Holders,
stating, among other things, that such registration statement has become
effective under the Securities Act and that (1) to the knowledge of such
counsel, no stop order suspending the


                                      A - 8

<PAGE>   9




effectiveness of such registration statement has been instituted or is pending
or contemplated under the Securities Act; and (2) the registration statement,
the related prospectus, and each amendment or supplement thereto, including all
documents incorporated by reference therein, comply as to form in all material
respects with the requirements of the Securities Act and the applicable rules
and regulations of the Commission thereunder (except that such counsel need
express no opinion as to financial statements or other financial or statistical
or reserve data contained or incorporated by reference therein); and such
counsel shall state in customary form that no facts have come to the attention
of such counsel that caused such counsel to believe (with customary
qualifications) that either the registration statement or the prospectus, or any
amendment or supplement thereto, including all documents incorporated by
reference therein, in light of the circumstances under which they were made,
contains any untrue statement of a material fact or omits to state a material
fact required to be stated therein or necessary to make the statements therein
not misleading (except that such counsel need express no belief as to financial
statements or other financial or statistical or reserve data contained or
incorporated by reference therein or as to any information provided by the
Holders or any underwriter for inclusion therein); and (B) a letter, dated such
date, from the independent certified public accountants of the Company,
addressed to the underwriters, if any, and to the Holders, stating, among other
things, that they are independent certified public accountants within the
meaning of the Securities Act and that in the opinion of such accountants, the
financial statements and other financial data of the Company included in the
registration statement or the prospectus, or any amendment or supplement
thereto, including all documents incorporated by reference therein, comply as to
form in all material respects with the applicable accounting requirements of the
Securities Act. Such letter from the independent certified public accountants
shall additionally cover such other customary financial matters (including
information as to the period ending not more than five business days prior to
the date of such letter) with respect to the registration in respect of which
such letter is being given as such underwriters, if any, or the Holders may
reasonably request;

                  (iii) prepare and file with the Commission a registration
statement with respect to such Registrable Securities and use its best efforts
to cause such registration statement to become and remain effective for a period
of not more than 90 days (or in the event of (A) a firm underwritten offering
such longer period as may be customary, or (B) the registration described in
Section 2(a)(iv), the period of time specified in such Section 2(a)(iv)), and
prepare and file with the Commission such amendments and supplements to such
registration statement and the prospectus used in connection therewith as may be
necessary to keep such registration statement effective during such period and
to comply with the provisions of the Securities Act with respect to the sale or
other disposition of all securities covered by such registration statement;
provided that no such registration statement or amendment thereto shall be filed
by the Company until the Holders of the Registrable Securities included therein
and their counsel shall have had a reasonable opportunity to review the same, to
exercise their rights under Section 2(c)(i) above with respect thereto and to
approve or disapprove any portion of such registration statement describing or
referring to such Holders;

                  (iv) furnish to each Holder and to each underwriter, if any,
such numbers of copies of a summary prospectus or other prospectus, including a
preliminary prospectus, in conformity with


                                      A - 9

<PAGE>   10




the requirements of the Securities Act, and such other documents, as such Holder
may reasonably request in order to facilitate the public sale or other
disposition of such Holder's Registrable Securities;

                  (v) notify the selling Holders promptly (A) when a
registration statement, prospectus, offering circular or other offering material
or any supplement or amendment thereto has been filed, and, with respect to a
registration statement or any post-effective amendment, when the same has become
effective under the Securities Act and each applicable state or foreign law, (B)
of any request by the Commission or any other United States or foreign federal
or state governmental authority for amendments or supplements to a registration
statement, or related prospectus (or other legally required offering material)
or for additional information, (C) of the issuance by the Commission or any
other United States or foreign federal or state governmental body or agency of
any action, including without limitation a stop order, suspending or withdrawing
the authorization for the offering or the effectiveness of a registration
statement, or the initiation of any proceedings for that purpose, (D) if at any
time the representations or warranties of the Company contained in any agreement
(including any underwriting, purchase or agency agreement) entered into in
connection with the offering or sale of securities of the Company as
contemplated by this Registration Rights Agreement cease to be true and correct
in any material respect, (E) of the receipt by the Company of any notification
with respect to the suspension of the qualification or exemption from
qualification of any of the Registrable Securities for sale in any jurisdiction
or the initiation or threatening of any proceeding for such purpose, (F) of the
discovery that, or of the happening of any event as a result of which, the
registration statement, related prospectus, offering circular, other offering
materials or any document incorporated or deemed to be incorporated therein by
reference includes an untrue statement of a material fact or omits to state any
material fact required to be stated therein or necessary to make the statements
therein not misleading, or that requires the making of any changes in such
registration statement, prospectus, offering circular or other offering
materials so that, in the case of the registration statement, it will not
contain any untrue statement of a material fact or omit to state any material
fact required to be stated therein or necessary to make the statements therein
not misleading, and that in the case of the prospectus, offering circular or
other offering materials, it will not contain any untrue statement of a material
fact or omit to state any material fact required to be stated therein or
necessary to make the statements therein, in light of the circumstances under
which they were made, not misleading, or that such document otherwise fails to
comply with applicable laws, and (G) of the Company's reasonable determination
that a post-effective amendment to a registration statement would be
appropriate;

                  (vi) use its best efforts to register or qualify the
Registrable Securities covered by such registration statement under the state
securities or blue sky laws of such United States jurisdictions as each Holder
shall request, and do any and all other acts and things which may be reasonably
necessary or advisable to enable such Holder to consummate the public sale or
other disposition in such United States jurisdictions of the Registrable
Securities owned by such Holder, except that the Company shall not for any such
purpose be required (A) to qualify to do business as a foreign corporation in
any jurisdiction wherein it is not so qualified, (B) to file therein any general
consent to service, or (C) to subject itself to taxation in any such
jurisdiction;


                                     A - 10

<PAGE>   11




                  (vii) in the event of the issuance of any stop order
suspending the effectiveness of any registration statement or of any order
suspending or preventing the use of any prospectus or suspending the
qualification of such Registrable Securities for sale in any jurisdiction, use
its reasonable efforts promptly to obtain its withdrawal;

                  (viii) if any event contemplated by Section 2(c)(v)(F) or (G)
above shall occur, as promptly as practicable prepare a supplement or amendment
or post-effective amendment to such registration statement, related prospectus,
offering circular or other offering materials or any document incorporated
therein by reference or promptly file any other required document so that, as
thereafter delivered to the purchasers of the Registrable Securities, the
prospectus, offering circular and other offering materials will not contain an
untrue statement of a material fact or omit to state any material fact required
to be stated therein or necessary to make the statements therein not misleading
or otherwise will not fail to comply with applicable law.

                  (ix) otherwise use its best efforts to comply with all
applicable rules and regulations of the Commission, and make available to its
security holders, as soon as reasonably practicable, an earnings statement
covering the period of at least twelve months, beginning with the first fiscal
quarter beginning after the effective date of the registration statement, which
earnings statement shall satisfy the provisions of Section 11(a) of the
Securities Act and Rule 158 thereunder; and

                  (x) list such securities on any securities exchange or
consolidated reporting system on which the Common Stock of the Company is then
listed, if the listing of such securities is then permitted under the rules of
such exchange or consolidated reporting system.

      (d) HOLDERS' OBLIGATIONS IN PIGGYBACK REGISTRATIONS. In connection with
any offering involving an underwriting of shares being issued by the Company,
the Company shall not be required to include any of the Holders' Registrable
Securities in such underwriting pursuant to Section 2(b) unless the Holders
accept the terms of the underwriting as agreed upon between the Company and the
underwriters; provided, however, that the only representations and warranties
any Holder shall be required to make in connection therewith shall be with
respect to such Holder's ownership of the Registrable Securities to be sold by
it and its ability to convey title thereto free and clear of all liens,
encumbrances or adverse claims and such other customary representations and
warranties reasonably requested by the underwriters; and provided further, that
the only indemnity any Holder shall be required to make in connection therewith
shall be to the effect of Sections 4(b) and 4(c) hereof.

      (e) PRICING OF PIGGYBACK REGISTRATIONS. The Registrable Securities
proposed to be registered under any registration statement under Section 2(b)
hereof shall be offered for sale at the same public offering price as the shares
of Common Stock offered for sale by the Company or any other selling shareholder
covered thereby.

      (f) PRIOR DEMAND RIGHT. Purchasers and each other Holder or Holders,
acknowledge and agree that their rights under Section 2 are subject to the prior
right of NBCC (i) to require demand


                                     A - 11

<PAGE>   12




registrations pursuant to article IV. B. of the Existing Registration Rights
Agreement and (ii) to the extent mandatorily applicable and not specifically
described herein, to certain of the rights to participate in incidental
registrations pursuant to article IV. A. of the Existing Registration Rights
Agreement, in each case of NBCC.

                                   SECTION 3.
                            EXPENSES OF REGISTRATION.

      All expenses incurred in connection with each registration of Registrable
Securities pursuant to Section 2(a) and any registration of Registrable
Securities pursuant to Section 2(b), including without limitation (i) all
Commission and state registration and qualification fees, (ii) all printing,
engineering and accounting fees, (iii) all fees and disbursements of counsel for
the Company, (iv) the fee payable to the National Association of Securities
Dealers, Inc., (v) all fees and disbursements of one law firm selected by the
Holders of a Majority of the Registrable Securities to be registered to
represent all the Holders, shall be borne by the Company, and (vi) all fees and
disbursements of any underwriters (including fees and disbursements of
underwriters' counsel, if applicable); provided, however, that the Company shall
not be required to pay, and the Holders shall pay, any underwriter discounts,
commissions and other underwriter compensation, to the extent such fees,
discounts, commissions and compensation relate to the Registrable Securities.

                                   SECTION 4.
                                INDEMNIFICATION.

      (a) In the event of any registration of Registrable Securities under the
Securities Act pursuant to this Registration Rights Agreement, the Company shall
indemnify and hold harmless the Holder of such Registrable Securities, such
Holder's directors and officers, and each other Person, if any, who controls
such Holder within the meaning of the Securities Act (a "Controlling Person"),
against any losses, claims, damages or liabilities, joint or several, to which
such Holder or any such director, officer or Controlling Person may become
subject under the Securities Act or any other statute or at common law, insofar
as such losses, claims, damages or liabilities (or actions in respect thereof)
arise out of or are based upon (i) any alleged untrue statement of any material
fact contained, on the effective date thereof, in any registration statement
under which such Registrable Securities were registered under the Securities
Act, or in any preliminary prospectus or final prospectus contained therein, or
any amendment or supplement thereto, or (ii) any alleged omission to state
therein a material fact required to be stated therein or necessary to make the
statements therein not misleading, and shall reimburse such Holder or such
director, officer or Controlling Person for any legal or any other expenses
reasonably incurred by such Holder, director, officer or Controlling Person in
connection with investigating or defending any such loss, claim, damage,
liability or action; provided, however, that the Company shall not be liable in
any such case to the extent that any such loss, claim, damage, liability or
action arises out of or is based upon any alleged untrue statement or alleged
omission made in such registration statement, preliminary prospectus,
prospectus, or amendment or supplement in reliance upon and in conformity with
written information furnished to the Company through an instrument duly executed
or provided by such


                                     A - 12

<PAGE>   13




Holder or an underwriter specifically for use therein. Such indemnity shall
remain in full force and effect regardless of any investigation made by or on
behalf of such Holder, director, officer or Controlling Person, and shall
survive the transfer of such Registrable Securities by such Holder.

      (b) It shall be a condition to the Company's obligation to register the
Registrable Securities of any Holder that such Holder shall enter into an
agreement to indemnify and hold harmless the Company, its directors and officers
and each other Person, if any, who controls the Company against any losses,
claims, damages or liabilities, joint or several, to which the Company or any
such director or officer or any such Person may become subject under the
Securities Act or any other statute or at common law, insofar as such losses,
claims, damages or liabilities (or actions in respect thereof) arise out of or
are based upon (i) any alleged untrue statement or omission of any material fact
contained, on the effective date thereof, in any registration statement under
which such Holder's Registrable Securities were registered under the Securities
Act, or in any preliminary prospectus or final prospectus contained therein, or
any amendment or supplement thereto, or (ii) any alleged omission to state
therein a material fact required to be stated therein or necessary to make the
statements therein not misleading, in each case to the extent, but only to the
extent, that such alleged untrue statement or omission was contained in written
information furnished to the Company through an instrument duly executed or
provided by such Holder specifically for use therein, and to reimburse the
Company or such director, officer or other Person for any legal or any other
expenses reasonably incurred in connection with investigating or defending any
such loss, claim, damage, liability or action.

      (c) Indemnification similar to that specified in Section 4(b)(i) and (ii)
above shall be given by the Company and each Holder (with such modifications as
shall be appropriate) to any underwriter with respect to any required
registration or other qualification of any Registrable Securities registered
under this Registration Rights Agreement under any federal or state law or
regulation of governmental authority. The indemnity and expense reimbursements
obligations of the Company and the Holders under Section 4(b)(i) and(ii) above
shall be in addition to any liability the Company and the Holders may otherwise
have.

      (d) Each Person (an "Indemnitor") who under the preceding provisions of
this Section 4 agrees to indemnify another Person (an "Indemnitee") shall have
the right, subject to the provisions hereto, to designate counsel (which counsel
shall be a nationally recognized securities law firm or a law firm acceptable to
the Holders) or to defend any case or proceeding against the Indemnitee arising
in respect of any claim of liability for which such indemnification may be
claimed, to the end that duplication of legal expense may be minimized; provided
that, if the Indemnitee notifies the Indemnitor that the former has been advised
by its counsel that any single counsel in such case or proceeding would have a
conflict of interest in representing both the Indemnitor and the Indemnitee, the
Indemnitee may designate one counsel of its own in such case or proceeding and,
to the extent so provided above in this Section 4, shall be entitled to be
reimbursed for its legal expenses reasonably incurred in connection with
defending itself in such case or proceeding.



                                     A - 13

<PAGE>   14




      (e) The Indemnitee shall give notice to the Indemnitor promptly after such
Indemnitee has actual knowledge of any claim as to which indemnity may be
sought, provided that the failure of any Indemnitee to give notice as provided
herein shall not relieve the Indemnitor of its obligations hereunder except to
the extent that the Indemnitor's defense of such claim is prejudiced thereby.

                                   SECTION 5.
                                  CONTRIBUTION.

      (a) In the event the indemnity provisions provided for in Section 4 of
this Registration Rights Agreement are for any reason held to be unenforceable
by the indemnified parties, the Company, the Holders and the underwriters, if
any, shall contribute to the aggregate losses, liabilities, claims, damages and
expenses of the nature contemplated by said indemnity provisions incurred by the
Company, the Holders and the underwriters in proportion to the relative fault of
each such party in connection with the statements or omissions that resulted in
such losses, liabilities, claims, damages and expenses. Relative fault shall be
determined by reference to, among other things, whether the untrue or alleged
untrue statement of a material fact or the omission or alleged omission to state
a material fact relates to information supplied by one of the parties and such
parties' relative intent, knowledge, access to information and opportunity to
correct or prevent such untrue statement or omission. Notwithstanding the
foregoing, no Holder shall be required to contribute, in the aggregate, any
amount in excess of the amount by which the total price at which the Registrable
Securities sold by it exceeds the amount of any damages that such Holder has
otherwise been required to pay by reason of such untrue or alleged untrue
statement or omission or alleged omission.

      (b) Notwithstanding the foregoing provisions of this Section 5, no person
guilty of fraudulent misrepresentation (within the meaning of Section 11(f) of
the 1933 Act) shall be entitled to contribution from any person who was not
guilty of such fraudulent misrepresentation. For purposes of this Section, each
person, if any, who controls an underwriter within the meaning of Section 15 of
the 1933 Act shall have the same rights to contribution as such underwriter, and
each director of the Company, each officer of the Company who signed such
registration statement and each person, if any, who controls the Company or any
Holder within the meaning of Section 15 of the 1933 Act shall have the same
rights to contribution as the Company or such Holder, as the case may be.

                                   SECTION 6.
                           SALES PURSUANT TO RULE 144.

      Upon written request, the Company shall deliver to any Holder a written
statement as to whether it has complied with all rules and regulations of the
Commission applicable in connection with use of Rule 144 (or any successor
thereto), including the timely filing of all reports required to be filed by the
Company with the Commission. The Company shall cause any restrictive legends to
be removed and any transfer restrictions to be rescinded with respect to any
sale of Registrable Securities which is exempt from registration under the
Securities Act pursuant to Rule 144.


                                     A - 14

<PAGE>   15





                                   SECTION 7.
                        TRANSFER OF REGISTRATION RIGHTS.

      The registration rights of Holders under this Registration Rights
Agreement may be assigned or transferred upon written notice to the Company to
any transferee acquiring Registrable Securities, other than in a public offering
pursuant to a registration statement or in a transaction pursuant to Rule 144.
Any transferee must acknowledge in writing its acceptance of all terms,
conditions and obligations of this Registration Rights Agreement.

                                   SECTION 8.
                                  TERMINATION.

      The Company shall not be obligated to take any action to effect any
registration, qualification or compliance pursuant to this Registration Rights
Agreement, and this Registration Rights Agreement shall terminate and be of no
force and effect (except any obligations of the Company under Section 6 of this
Registration Rights Agreement) with respect to any Holder (and such Holder only)
who may sell all of such Holder's Registrable Securities in reliance upon Rule
144(k) (or any successor rule) promulgated under the Securities Act.

                                   SECTION 9.
                                    REMEDIES.

      The Company recognizes that money damages may be inadequate to compensate
the Holders for a breach by the Company of its obligations under this
Registration Rights Agreement, and the Company agrees that in the event of such
a breach any of the Holders may apply for an injunction of specific performance
or the granting of such other equitable remedies as may be awarded by a court of
competent jurisdiction in order to afford the Holders the benefits of this
Registration Rights Agreement and that the Company shall not object to such
application, entry of such injunction or granting of such other equitable
remedies on the grounds that money damages shall be sufficient to compensate the
Holders.

                                   SECTION 10.
                        PRIORITY OF REGISTRATION RIGHTS.

      The Company shall not grant to any Person while this Registration Rights
Agreement remains in effect the right to request the Company to register any
securities of the Company under the Securities Act which right has priority over
or is inconsistent with the rights granted to the Holders hereby.



                                     A - 15

<PAGE>   16




                                   SECTION 11.
                                 MISCELLANEOUS.

      (a) NOTICES.

          (i)  All communications under this Registration Rights Agreement shall
be in writing and shall be sent:

               (A) if to any party hereto at its address or facsimile number for
notices specified beneath its name on the signature page hereof, or at such
other address or facsimile number as it may have furnished in writing to each
other party hereto;

               (B) if to any other person or entity who is the registered holder
of any Registrable Securities to the address or facsimile number of such holder
as it appears in the stock ledger of the Company.

          (ii) Any notice shall be deemed to have been duly given and received
(A) at the time of delivery when delivered by hand, if personally delivered, (B)
if sent by mail, two business days after being deposited in the mail, postage
prepaid, return receipt requested, and (C) when sent by facsimile, with
confirmation of receipt, so long as a duplicate of such notice is deposited in
the mail, first class postage prepaid, on the date such facsimile is sent.

      (b) SUCCESSORS AND ASSIGNS. This Agreement shall inure to the benefit of
and be binding upon the permitted successors and assigns of each of the parties
whether so expressed or not.

      (c) AMENDMENT AND WAIVER. ETC. This Agreement may be amended, and the
observance of any term of this Registration Rights Agreement may be waived, but
only with the written consent of the Company and the Holders of a Majority of
the Registrable Securities. No failure or delay on the part of the Holders in
exercising any right, power or remedy hereunder shall operate as a waiver
thereof, nor shall any single or partial exercise of any such right, power or
remedy preclude any other or further exercise thereof or the exercise of any
other right, power or remedy. The remedies provided for herein are cumulative
and are not exclusive of any remedies that may be available to the Holders at
law or in equity or otherwise. No waiver of or consent to any departure by the
Company from any provision of this Registration Rights Agreement shall be
effective unless in writing and signed by the Holders of a Majority of the
Registrable Securities.

      (d) DUPLICATE ORIGINALS. Two or more duplicate originals of this
Registration Rights Agreement may be signed in counterpart by the parties, each
of which shall be an original but all of which together shall constitute one and
the same instrument.

      (e) SEVERABILITY. In the event that any one or more of the provisions
contained herein, or the application thereof in any circumstance, is held
invalid, illegal or unenforceable, the validity,


                                     A - 16

<PAGE>   17




legality and enforceability of any such provision in every other respect and of
the remaining provisions contained herein shall not be affected or impaired
thereby.

      (f) GOVERNING LAW. This Agreement shall be governed by and construed in
accordance with the substantive law of Texas without giving effect to the
principles of conflicts of law thereof.

      (g) ENTIRE AGREEMENT. This Agreement constitutes and contains the entire
agreement of the parties and supersedes any and all prior negotiations,
correspondence, undertakings and agreements between the parties hereto
respecting the subject matter hereof.

      IN WITNESS WHEREOF, the parties hereto have executed and delivered this
Registration Rights Agreement as of the date first above written.

                             COSTILLA ENERGY, INC.,
                             a Delaware corporation
                             400 West Illinois, Suite 1100
                             Midland, Texas 79701
                             Facsimile: (915) 686-6080
                             Attention:  President and Chief Executive Officer


                             By: /s/
                                ------------------------------------------
                             Name:
                                  ---------------------------------------- 
                             Title:
                                   ---------------------------------------     


                             ENRON CAPITAL & TRADE RESOURCES CORP.,
                             a Delaware corporation
                             1400 Smith
                             Houston, Texas  77002
                             Facsimile:  (713) 646-3640
                             Attention:  Timothy J. Detmering, Vice President

                             With a copy to:
                             Donna W. Lowry
                             Facsimile: (713) 646-4039

                             
                             By: /s/
                                ------------------------------------------
                             Name:
                                  ----------------------------------------
                             Title:
                                   ---------------------------------------



                                     A - 17

<PAGE>   18



                             JOINT ENERGY DEVELOPMENT INVESTMENTS II
                               LIMITED PARTNERSHIP

                             By:   Enron Capital Management Limited Partnership,
                                   its General Partner

                             By:   Enron Capital II Corp.,
                                   its General Partner

                             By: /s/
                                ------------------------------------------
                             Name:
                                  ----------------------------------------
                             Title:
                                    -------------------------------------- 
      

                                     A - 18