1

                                                                     EXHIBIT 5.1


                                  Law Offices
                                 McAFEE & TAFT
                           A Professional Corporation
                       10th Floor, Two leadership Square
                               211 North Robinson
                       Oklahoma City, Oklahoma 73102-7103
                                 (405) 235-9621

                                  June 29, 2001


Fleming Companies, Inc.
P.O. Box 299013
Lewisville, Texas  75029

                                Re:     Resale of Common Stock by U.S.
                                        Transportation, LLC

Ladies and Gentlemen:

                Reference is made to your Registration Statement on Form S-3 to
be filed with the Securities and Exchange Commission today with respect to the
sale by U.S. Transportation, LLC of 3,850,301 shares of common stock of Fleming
Companies, Inc., $2.50 par value per share (the "Common Stock"). The Common
Stock was issued pursuant to a Stock and Warrant Purchase Agreement by and
between Fleming Companies, Inc., as Issuer, and U.S. Transportation, LLC, as
Investor, dated as of February 6, 2001.

                We have examined such corporate records and made such other
investigations as we deemed appropriate for the purposes of this opinion.

                Based upon the foregoing, we are of the opinion that:

                1. The Company has been duly incorporated and is validly
existing and in good standing under the laws of Oklahoma.

                2. The shares of Common Stock have been validly issued and are
fully paid and nonassessable.

                We hereby consent to the inclusion of this opinion as an exhibit
to the above mentioned registration statement.


                                            Very truly yours,


                                            /s/ MCAFEE & TAFT