1
                                                                EXHIBIT 8.1



               [Letterhead of Cleary, Gottlieb, Steen & Hamilton]







Writer's Direct Dial: (212) 225-2360



                                              November 12, 1996


Boatmen's Bancshares, Inc.
One Boatmen's Plaza
800 Market Street
St. Louis, Missouri 63101

Ladies and Gentlemen:

        You have requested our opinion regarding certain U.S. federal income tax
consequences of the proposed merger (the "Merger") of Boatmen's Bancshares,
Inc., a Missouri corporation ("Boatmen's"), and NB Holdings Corporation, a
Delaware corporation (the "Merger Sub") and a direct subsidiary of NationsBank
Corporation, a North Carolina corporation ("NationsBank"). The Merger is to be
effected pursuant to the Agreement and Plan of Merger dated as of August 29,
1996 between Boatmen's, NationsBank and the Merger Sub (the "Merger
Agreement"). Defined terms used but not defined herein have the same meaning as
in the Merger Agreement.

        In arriving at the opinions expressed below, we have examined and
relied on the originals, or copies certified or otherwise identified to our
satisfaction, of:

        (i)     the Merger Agreement;

        (ii)    the Prospectus and Joint Proxy Statement included in the
                Registration Statement on Form S-4 filed with the Securities and
                Exchange Commission by NationsBank in connection with the Merger
                (the "Prospectus"); and 
   2
Boatmen's Bancshares, Inc., p.2

                (iii)   such corporate records of Boatmen's, NationsBank and
                        the Merger Sub as we have deemed appropriate.

                We have also relied, without independent verification of the
statements contained therein, on Officer's Certificates of Boatmen's,
NationsBank and the Merger Sub, each dated the date hereof (the "Certificates"),
containing representations as to certain tax matters. We have assumed that the
parties to the Merger will act, and the Merger will be effected, in accordance
with the Merger Agreement and that the representations contained in the
Certificates are accurate. In addition, we have made such other investigations 
of law as we have deemed appropriate as a basis for the opinions expressed
below.

                The opinion contained herein is being provided in advance of
the actual Merger in compliance with certain requirements of the Securities and
Exchange Commission and assumes that all subsequent events will be in accordance
with the Merger Agreement.

                We express no opinion as to the laws of any jurisdiction other
than the income tax laws of the United States.

                Based upon and subject to the foregoing, it is our opinion that
for U.S. federal income tax purposes, under current law:

                (a)     The Merger will constitute a reorganization within the
        meaning of Section 368(a) of the Internal Revenue Code of 1986, as
        amended (the "Code");

                (b)     Each of Boatmen's, NationsBank and the Merger Sub will
        be a party to the reorganization within the meaning of Section 368(b) of
        the Code;

                (c)     No gain or loss will be recognized by Boatmen's in
        connection with the Merger;

                (d)     No gain or loss will be recognized by the stockholders
        of Boatmen's on the exchange of their shares of Boatmen's stock solely
        for shares of NationsBank stock pursuant to the terms of the Merger
        Agreement to the extent of such exchange (except as provided below with
        respect to fractional shares);

                (e)     The federal income tax basis of the shares of the
        NationsBank stock for which the shares of Boatmen's stock are exchanged
        solely therefor pursuant to the Merger will be the same as the tax basis
        of such shares of Boatmen's stock exchanged solely therefor (less any
        proportionate part of such basis allocable to any fractional interest in
        any share of NationsBank Common Stock);

                (f)     The holding period for the shares of NationsBank stock
        for which the shares of Boatmen's stock are exchanged will include the
        holding period of the shares of
   3
Boatmen's Bancshares, Inc., p. 3




        Boatmen's stock that they exchanged therefor, provided that such shares
        of Boatmen's stock are held as a capital asset at the Effective Time;
        and

                (g)     The receipt of cash in lieu of fractional shares will be
        treated as if the fractional shares were distributed as part of the
        exchange and then redeemed by NationsBank, and gain or loss will be
        recognized in an amount equal to the difference


        between the cash received and the tax basis of the NationsBank Common
        Stock surrendered, which gain or loss will be capital gain or loss if
        the Boatmen's Common Stock was a capital asset in the hands of the
        shareholder.

                We hereby consent to the use of our name and the making of
statements with respect to us under the captions "SUMMARY--Certain Federal
Income Tax Consequences" and "THE MERGER--Certain Federal Income Tax
Consequences" in the Prospectus.

                In giving this consent, we do not hereby admit that we are in
the category of persons whose consent is required under Section 7 of the
Securities Act of 1933 as amended.

                                        Very truly yours,

                                        CLEARY, GOTTLIEB, STEEN & HAMILTON


                                        By:  /s/ Dana L. Trier
                                             ------------------------------
                                               Dana L. Trier, a Partner