Exhibit 99.1

NYTEX Announces Exploration of Possible Series A Convertible Preferred Stock Restructuring

DALLAS, June 1, 2012 — NYTEX Energy Holdings, Inc. (“NYTEX” OTCQB: NYTE) announced today that its Board of Directors is exploring the possible restructuring of certain of the terms and conditions of its outstanding shares of Series A Convertible Preferred Stock (the “Preferred Stock”), including, among other things, restructuring the approximately $746,000 of currently accrued but unpaid dividends with respect to the Preferred Stock, in order to potentially strengthen NYTEX’s balance sheet, provide greater operating and financing flexibility, and better position NYTEX to take advantage of business opportunities that may present themselves to NYTEX in the future. No decision has been made to engage in any transaction or transactions that may result from the Board of Directors’ exploration of any such possible restructuring, and there can be no assurance that any such restructuring will occur or, if undertaken, the terms or timing thereof. NYTEX does not intend to disclose developments with respect to the progress of its review of any such possible restructuring until such time as the Board of Directors has approved a transaction, if any, or otherwise deems disclosure appropriate.

About NYTEX Energy Holdings, Inc.

NYTEX Energy Holdings, Inc. (website: http://nytexenergyholdings.com) is a Dallas-based energy holding company consisting of two subsidiaries, NYTEX Petroleum, Inc. and Petro Staffing Group, LLC. NYTEX Petroleum, Inc., a wholly-owned subsidiary, is engaged in the acquisition, development, and resale of oil and gas leasehold properties in Texas. NYTEX Petroleum, Inc. also acquires overriding royalty and working interests in the leasehold properties’ production of oil and gas reserves. Petro Staffing Group, LLC is a full-service staffing agency providing the energy marketplace with temporary and full-time professionals. NYTEX Energy owns 80% of Petro Staffing Group, LLC.

This press release includes “forward-looking statements,” which may include information concerning the company’s plans, objectives, goals, strategies, future revenues or performance, capital expenditures, financing needs and other information that is not historical information. When used in this release, the words “will,” “intends,” “expects,” “outlook,” “forecast,” “estimates,” “anticipates,” “projects,” “plans,” “believes,” and variations of such words or similar expressions are intended to identify forward-looking statements. All forward-looking statements are based upon current expectations and beliefs and various assumptions. There can be no assurance that the company will realize these expectations or that these beliefs will prove correct. The company’s ability to achieve the financial targets described in this press release is subject to numerous factors and contingencies, many of which are beyond the company’s control. These include local and national economic, credit and capital market conditions, including prevailing interest rates; legal and regulatory developments, including changes to tax rates, applicable securities regulations or accounting standards, and ability to obtain necessary licenses and permits; and geopolitical conditions, including the occurrence of acts of war or terrorist incidents, and weather or natural disasters. Any of these factors or others not named herein could cause the company’s actual results to differ materially from those expressed as forward-looking statements. In addition, other risk factors that could cause actual results to differ materially from the forward-looking statements contained in this release include those that are discussed in the company’s filings with the Securities and Exchange Commission. Any forward-looking statement speaks only as of the date on which it is made, and the company undertakes no, and expressly disclaims any, obligation to update any forward-looking statement to reflect events or circumstances after the date on which it is made or to reflect the occurrence of anticipated or unanticipated events or circumstances.

Contact Information:

NYTEX Energy Holdings, Inc.

Bryan A. Sinclair

(972) 770-4700