Exhibit 5.1

MCGRATH NORTH MULLIN & KRATZ, PC LLO

SUITE 3700 FIRST NATIONAL TOWER

1601 DODGE STREET

OMAHA, NEBRASKA 68102

PH: (402) 341-3070

July 26, 2013

Supertel Hospitality, Inc.

1800 West Pasewalk Avenue, Suite 200

Norfolk, NE 68701

Ladies and Gentlemen:

We have acted as counsel to Supertel Hospitality, Inc., a Virginia corporation (the “Company”), in connection with a Registration Statement on Form S-11 (the “Registration Statement”) filed with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Act”), with respect to the offer and sale of shares of common stock of the Company, par value $0.01 per share (the “Common Stock”) having an aggregate offering price of up to $115,000,000.

In connection with our opinion, we have relied upon, among other things, our examination of such documents, records of the Company and certificates of its officers and public officials as we have deemed necessary for purposes of the opinions expressed below. In our examination of the foregoing, we have assumed the genuineness of all signatures, the legal capacity of all natural persons, the accuracy and completeness of all documents submitted to us, the authenticity of all original documents, and the conformity to authentic original documents of all documents submitted to us as copies.

Based upon the foregoing, and having regard for such legal considerations as we have deemed relevant, we are of the opinion that:

1. The Company has been duly incorporated and is validly existing as a corporation in good standing under the laws of the Commonwealth of Virginia.

2. When (a) the Registration Statement becomes effective under the Act, and (b) the Common Stock has been issued and sold upon the terms and conditions set forth in the Registration Statement against payment of the consideration set forth therein, then such Common Stock will be legally issued, fully paid and non-assessable.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement. We also consent to the references to McGrath North Mullin & Kratz, PC LLO under the caption “Legal Matters” in the prospectus comprising a part of the Registration Statement. In giving this consent, we do not admit that we are in the category of persons whose consent is required by Section 7 of the Securities Act of 1933, as amended, or the rules and regulations promulgated thereunder by the SEC.

Yours very truly,

/s/ McGrath North Mullin & Kratz, PC LLO

McGrath North Mullin & Kratz, PC LLO