Exhibit 99.1

Vermillion Announces CEO Succession Plan

AUSTIN, Texas — May 15, 2012 — The board of directors of Vermillion, Inc. (NASDAQ: VRML), a leading molecular diagnostics company, has begun the process of identifying a successor to Gail S. Page, president and CEO. The board has formed a search committee, with the goal of completing the search by September 2012.

James S. Burns, Vermillion’s chairman of the board, commented: “During her tenure, Gail led the divestiture of the company’s original research tools business, obtained FDA approval for OVA1^® (the first proteomic IVDMIA to be cleared by the FDA), launched and commercialized OVA1 with Quest Diagnostics, created a molecular diagnostic development pipeline, and most recently, resolved major long-standing pieces of litigation with favorable outcomes for the company.”

“Vermillion now enters a new commercial phase,” continued Burns, “one in which we can expand the market for OVA1, continue OVA2^™ and PAD development, and seek additional opportunities for Vermillion to build a molecular diagnostic franchise both on its own and in partnership with other companies. A leadership change at this point is consistent with our plans to advance the company to its next phase of growth. On behalf of the entire board, I would like to thank Gail for her dedication and outstanding service to Vermillion. Her achievements have been key to both the survival and early growth of our company. We wish her the very best in her new endeavors and look forward to a smooth transition.”

Page commented: “I would like to thank the board, our shareholders and my colleagues who provided the opportunity to lead Vermillion during my tenure. The company has succeeded in a true pioneering effort, thanks to the hard work of its management and employees. I would especially like to thank those who worked tirelessly to help make OVA1 a life-saving test for the women who face the challenges associated with ovarian cancer. The company has a solid foundation for the future, and I remain committed to the tasks at hand and the smooth transition to a new president and CEO. The company has a first-class management team in place, and I am grateful for their support and that of our customers and collaborators.”

As part of the leadership succession plan, Page has resigned from the board of directors.

About OVA1

OVA1 is a blood test for pre-surgical assessment of ovarian tumors for malignancy, using a unique multi-biomarker approach. In a published clinical trial, OVA1 achieved 99% sensitivity in detecting epithelial ovarian cancers (EOC). This included 96% sensitivity for stage I EOC, the earliest and most curable EOC stage, compared with 57% for the conventional biomarker CA125.(1) In addition, OVA1 found 70% of malignancies missed by non-specialist pre-surgical assessment,(1) and it increased detection of malignancy over ACOG guidelines from 77% to 94%.(2) As the first protein-based, In Vitro Diagnostic Multi-Variate Index Assay (IVDMIA) cleared by the FDA, OVA1 also represents a new class of software-based diagnostics.

1

Citings:

About Vermillion

Vermillion, Inc. (NASDAQ: VRML) is dedicated to the discovery, development and commercialization of novel high-value diagnostic tests that help physicians diagnose, treat and improve outcomes for patients. Vermillion, along with its prestigious scientific collaborators, has diagnostic programs in oncology, hematology, cardiology and women’s health. Additional information about Vermillion can be found at www.vermillion.com.

Forward-Looking Statement

Certain matters discussed in this press release contain forward-looking statements that involve significant risks and uncertainties, including statements regarding Vermillion’s plans, objectives, expectations and intentions. These forward-looking statements are based on Vermillion’s current expectations. The Private Securities Litigation Reform Act of 1995 provides a “safe harbor” for such forward-looking statements. In order to comply with the terms of the safe harbor, Vermillion notes that a variety of factors could cause actual results and experience to differ materially from the anticipated results or other expectations expressed in such forward-looking statements. Factors that could cause actual results to materially differ include but are not limited to: (1) uncertainty as to Vermillion’s ability to protect and promote its proprietary technology; (2) Vermillion’s lack of a lengthy track record successfully developing and commercializing diagnostic products; (3) uncertainty as to whether Vermillion will be able to obtain any required regulatory approval of its future diagnostic products; (4) uncertainty of the size of market for its existing diagnostic tests or future diagnostic products, including the risk that its products will not be competitive with products offered by other companies, or that users will not be entitled to receive adequate reimbursement for its products from third party payors such as private insurance companies and government insurance plans; (5) uncertainty that Vermillion has sufficient cash resources to fully commercialize its tests and continue as a going concern; (6) uncertainty whether the trading in Vermillion’s stock will become significantly less liquid; and (7) other factors that might be described from time to time in Vermillion’s filings with the Securities and Exchange Commission. All information in this press release is as of the date of this report, and Vermillion expressly disclaims any obligation or undertaking to release publicly any updates or revisions to any such statements to reflect any change in Vermillion’s expectations or any change in events, conditions or circumstances on which any such statement is based, unless required by law.

This release should be read in conjunction with the consolidated financial statements and notes thereto included in our most recent reports on Form 10-K and Form 10-Q. Copies are available through the SEC’s Electronic Data Gathering Analysis and Retrieval system (EDGAR) at www.sec.gov.

Investor Relations:

Liolios Group, Inc.

Ron Both

Tel 949-574-3860

vrml@liolios.com

2