Exhibit 99.1

NEWS RELEASE

Tuesday, May 17, 2005

FOR IMMEDIATE RELEASE

PETRO STOPPING CENTERS HOLDINGS ANNOUNCES RESTATEMENT OF ITS

ACCOUNTING FOR LEASES AND RELATED DEPRECIATION

EL PASO, Texas, May 17, 2005 — Petro Stopping Centers Holdings, L.P. today announced that the Company has determined that it had incorrectly calculated its depreciation expenses. As a result, the Company will restate its financial statements for the three-year period ended December 31, 2004.

The restatement relates to the Company’s previous depreciation of its leasehold improvements, in some cases, over a period greater than both the initial term of the lease and its option periods, but not longer than the useful life of the asset. After an analysis of the Company’s records on May 13, 2005, the Company has concluded that it should use the shorter of (1) the initial lease term unless it believes that the penalty for not renewing the lease would be substantial enough that it was “reasonably assured” that the Company would exercise the renewal, or (2) the useful life of the asset. The restatement relates, in part, to the February 7, 2005 letter issued by the Office of the Chief Accountant of the Securities and Exchange Commission to the American Institute of Certified Public Accountants, which clarified the existing generally accepted accounting principles applicable to leases.

The Company believes these non-cash adjustments, which are similar to those recently announced by other public companies related to leases, will have no material impact on the Company’s previously reported cash flows, cash position, revenues, or EBITDA in any period, or on compliance with the covenants under its senior secured credit facilities, Indentures for the 9.0% senior secured notes due 2012, and Indentures for the new senior third secured discount notes due 2014.

Although the Company continues to analyze the proper accounting treatment, the Company currently estimates the cumulative effect of the restatement of financial statements through December 31, 2004 will reduce retained earnings by approximately $805,000, reflecting increased accumulated depreciation and depreciation expense. Of the $805,000, $618,000 is anticipated to be reflected in periods prior to December 31, 2001. The Company anticipates that that depreciation will be increased (and operating income decreased) by $128,000, $21,000, and $38,000 for the periods ending December 31, 2002, 2003, and 2004, respectively.

These estimates are subject to change as the Company completes its preparation of the restated financial statements. The Company will amend the appropriate filings with the Securities and Exchange Commission to include the restated financial statements for the three-year period ended December 31, 2004. As a result of the restatement, the financial statements contained in the Company’s prior filings with the Securities and Exchange Commission, should no longer be relied upon.

ABOUT PETRO

Petro Stopping Centers Holdings, L.P., a Delaware limited partnership, was formed on July 23, 1999, as a holding partnership and conducts substantially all of its operations through Petro Stopping Centers, L.P., a leading owner and operator of large, multi-service truck stops. Since it opened its first Petro Stopping Center in 1975, its nationwide network has grown to 62 facilities located in 31 states. Of these locations, 40 are company-operated and 22 are franchised. The Company’s facilities are situated at convenient locations with easy highway access and target the unique needs of professional truck drivers. Petro Stopping Centers offer a broad range of products, services, and amenities, including diesel fuel, gasoline, home-style Iron Skillet^{^®} restaurants, Petro:Lube^{^®} truck maintenance and repair services, and travel and convenience stores.

FORWARD-LOOKING STATEMENTS

All statements contained in this press release that are not historical facts are forward-looking statements under the federal securities laws. These forward-looking statements are not guarantees of future performance and inherently involve certain risks, uncertainties and

assumptions that are difficult to predict. These statements are based on the Company’s estimates, actual outcomes and results may differ materially from what is expressed in, or implied by, such forward-looking statements. Petro Stopping Centers, L.P. assumes no obligation to publicly update or revise any forward-looking statement, whether as a result of new information, future events, or otherwise.

# # #

FOR ADDITIONAL INFORMATION

Mr. Edward Escudero

Treasurer and Chief Financial Officer

(915) 779-4711

PETRO STOPPING CENTERS HOLDINGS LP 8-K