Lehman Brothers to Explore Strategic Alternatives for Pipeline Unit

May 12, 2005, New York, NY

Southern Star Central Corp. (SSTAR) announced today that it has engaged Lehman Brothers as its financial advisor to explore strategic alternatives available to Southern Star’s shareholders, which may include an MLP, an IPO, sale, or other alternatives of its Owensboro-based Southern Star Central Gas Pipeline, Inc. business unit.

Michael J. Walsh, a director of Southern Star Central Corp. and Chief Executive Officer of Southern Star Central Gas Pipeline said in a communication to its 458 employees, “The decision to explore the strategic alternatives available to the Southern Star’s shareholders at this time reflects the tremendous successes that we have achieved at Southern Star since AIG Highstar’s acquisition of the company in 2002, as well as the recent valuations that have been realized for similar businesses.” He further stated, “The successes we have enjoyed at Southern Star include the transition from the prior owner and establishment of Southern Star as an independent company with a unique and entrepreneurial culture, the issuance of public debt, the completion of our new headquarters, the investment in and improvement of our existing business and assets, the identification and development of new markets and customers, the renewed commitment to our communities, and the recent completion of our rate case, are all achievements in which every employee can take a tremendous sense of pride and accomplishment. We have accomplished more in the past 2 ½ years than many companies accomplish in decades.”

The Southern Star Board and its advisors have begun working with the Southern Star management team to prepare due diligence materials and supporting data. It is anticipated that this work will be complete over the course of the next several weeks and a decision on a course of action will come shortly thereafter. No assurance, however, can be given that any strategic alternative explored by Southern Star will be adopted, and if adopted, consummated.

Contacts:

About Southern Star Central Corp

Southern Star Central Corp. (SSTAR) is the parent of Southern Star Central Gas Pipeline, Inc., a natural gas transmission system headquartered in Owensboro, Kentucky, spanning over 6,000 miles in the Midwest and Mid-continent regions of the United States. The pipeline system and facilities are located throughout Kansas, Oklahoma, Missouri, Wyoming, Nebraska, Colorado, Texas. It serves major markets such as Kansas City, Wichita, Springfield, and St. Louis.

Safe Harbor Statement

Statements made by Southern Star in this press release relating to future plans and events are “forward-looking statements” within the meaning of the Private Securities Litigation Reform Act of 1995. These forward-looking statements are based on Southern Star’s current plans and expectations and involve a number of risks and uncertainties that could cause actual events to differ materially from those contemplated by the forward-looking statements, including, without limitation, future utilization of pipeline capacity; operational risks and limitations of the company’s pipeline system; the ability to raise capital in a cost-effective manner; changes in federal, state or local laws and regulations to which the company is subject; the ability to manage costs; environmental risks; governmental regulations; legal and administrative proceedings; restrictive covenants contained in various instruments applicable to the company; changes in general economic, market or business conditions; and acts of war or terrorist activities.

These and other risk factors are discussed in Southern Star’s Annual Report on Form 10-K and in its other filings with the SEC. In addition, the forward-looking statements included in this press release are as of May 12, 2005. While Southern Star may elect to update these forward-looking statements at some point in the future, it specifically disclaims any obligation to do so.

Form 8-K