Exhibit 99.1

News Release

General Inquiries: 877.847.0008

www.constellationenergypartners.com

Investor Contact: Charles C. Ward 877.847.0009

Constellation Energy Partners

Provides Update on Management Initiatives

• Board of Managers Adopts 2009 Omnibus Incentive Compensation Plan

• Employment Agreements Executed With Key Executives

HOUSTON—(BUSINESS WIRE)—May 4, 2009—Constellation Energy Partners (NYSE Arca: CEP) today announced that its Board of Managers has taken several measures to further align its management and employees to the objectives and performance of the company.

The company’s Board of Managers adopted and approved the 2009 Omnibus Incentive Compensation Plan (“Omnibus Plan”) on April 28, 2009. A total of 1,650,000 common units may be made available for grants to employees, including key executives, under the Omnibus Plan. The company’s existing Long-Term Incentive Plan (“LTIP”), which makes an additional 450,000 common units available for grants, is not affected by adoption of the Omnibus Plan. Approximately 410,421 common units remain available for grants under the LTIP.

The Omnibus Plan is subject to approval by common and Class A unitholders under the terms of the company’s Operating Agreement. The company anticipates submitting the Omnibus Plan for approval by common and Class A unitholders at its next annual meeting, the date for which has not yet been set. Details of the Omnibus Plan, which is subject to change as a result of market conditions, will be provided to common and Class A unitholders with the company’s proxy statement in advance of the annual meeting.

The company also announced that it has entered into definitive employment agreements with its key executives, including Stephen R. Brunner, the company’s President, Chief Executive Officer and Chief Operating Officer; Charles C. Ward, the company’s Chief Financial Officer

and Treasurer; Lisa J. Mellencamp, the company’s General Counsel and Secretary; and Michael B. Hiney, the company’s Chief Accounting Officer and Controller. The employment agreements replace employment letter agreements executed with each of Mr. Brunner, Mr. Ward, Ms. Mellencamp and Mr. Hiney in January 2009. Each employment agreement has a primary term of three years.

As part of their total compensation package, Mr. Brunner, Mr. Ward, Ms. Mellencamp, and Mr. Hiney were granted an aggregate of 161,871 restricted common units which vest over a two year period and are subject to forfeiture under certain circumstances, including termination of employment. The Compensation Committee of the Board of Managers made these grants based on the employment inducement exemption provided under the corporate governance listing standards of the New York Stock Exchange (NYSE) Arca. As a result, the grants did not require approval by the company’s unitholders, and this press release is being issued in accordance with NYSE Arca rules.

The employment agreements and related grants were approved by the Compensation Committee of the company’s Board of Managers, which is composed solely of independent managers.

Additional information about the Omnibus Plan and employment agreements will be made available in the company’s public filings with the Securities and Exchange Commission.

About the Company

Constellation Energy Partners LLC (http://www.constellationenergypartners.com) is a limited liability company focused on the acquisition, development and production of oil and natural gas properties, as well as related midstream assets.

Forward-Looking Statements

We make statements in this news release that are considered forward-looking statements within the meaning of the Securities Act of 1933 and the Securities Exchange Act of 1934. These forward-looking statements are largely based on our expectations, which reflect estimates and assumptions made by our management. These estimates and assumptions reflect our best judgment based on currently known market conditions and other factors. Although we believe such estimates and assumptions to be reasonable, they are inherently uncertain and involve a number of risks and uncertainties that are beyond our control. In addition, management’s

- 2 -

assumptions about future events may prove to be inaccurate. Management cautions all readers that the forward-looking statements contained in this news release are not guarantees of future performance, and we cannot assure you that such statements will be realized or the forward-looking events and circumstances will occur. Actual results may differ materially from those anticipated or implied in the forward-looking statements due to factors listed in the “Risk Factors” section in our SEC filings and elsewhere in those filings. All forward-looking statements speak only as of the date of this news release. We do not intend to publicly update or revise any forward-looking statements as a result of new information, future events or otherwise.

- 3 -