Exhibit 5.1

BRACEWELL & GIULIANI LLP

711 Louisiana Street, Suite 2300

Houston, Texas 77002-2770

(713) 223-2300

May 18, 2012

Key Energy Services, Inc.

1301 McKinney Street, Suite 1800

Houston, Texas 77010

Re:     Key Energy Services, Inc. 2012 Equity and Cash Incentive Plan

Ladies and Gentlemen:

We have acted as counsel to Key Energy Services, Inc., a Maryland corporation (the “Company”), in connection with the preparation of the Company’s Registration Statement on Form S-8 (the “Registration Statement”) to be filed with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”), relating to the registration and proposed offer and sale of up to 4,000,000 shares of the Company’s common stock, par value $0.10 per share (the “Shares”), pursuant to the terms of awards granted under the Key Energy Services, Inc. 2012 Equity and Cash Incentive Plan (the “Plan”). This opinion is being furnished to you for filing as an exhibit to the Registration Statement.

In connection with rendering this opinion, we have examined (1) the Registration Statement; (2) the Company’s charter as set forth in its Articles of Restatement; (3) the Company’s By-Laws, as amended and restated; (4) the Plan; (5) certain resolutions of the Board of Directors of the Company; and (6) such other documents and records as we have deemed necessary and relevant for purposes hereof. In addition, we have relied upon certificates of officers of the Company and of public officials as to certain matters of fact relating to this opinion and have made such investigations of law as we have deemed necessary and relevant as a basis hereof. In such examination, we have assumed the genuineness of all signatures, the authenticity of all documents, certificates and records submitted to us as originals, the conformity to original documents, certificates and records of all documents, certificates and records submitted to us as copies, and the truthfulness of all statements of fact contained therein. In addition, we have assumed that the Registration Statement has been filed with the Commission and has become effective under the Act.

Based upon the foregoing and subject to the limitations and assumptions set forth herein and having due regard for such legal considerations as we deem relevant, we are of the opinion that the Shares have been duly and validly authorized, and, when issued and paid for in accordance with the Plan and the provisions of the award agreements relating to awards granted under the Plan, the Shares will be validly issued, fully paid and nonassessable.

The foregoing opinion is based on and is limited to the law of the State of Maryland and the relevant law of the United States of America, and we render no opinion with respect to the laws of any other jurisdiction.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement and to the use of our name therein. By giving such consent, we do not admit that we are in the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

/s/ BRACEWELL & GIULIANI LLP

Bracewell & Giuliani LLP