Exhibit 5.1

MCGRATH NORTH MULLIN & KRATZ, PC LLO

SUITE 3700 FIRST NATIONAL TOWER

1601 DODGE STREET

OMAHA, NEBRASKA 68102

PH: (402) 341-3070

March 31, 2011

Supertel Hospitality, Inc.

309 N. 5th Street

Norfolk, NE 68701

Ladies and Gentlemen:

We have acted as counsel to Supertel Hospitality, Inc., a Virginia corporation (the “Company”), in connection with the Company’s registration statement on Form S-3 (registration number 333-170756) (the “Registration Statement”) relating to the proposed issuance and sale by the Company from time to time, pursuant to Rule 415 under the Securities Act of 1933, as amended (the “Securities Act”) of up to $20,000,000 of securities of the Company as set forth in the Prospectus dated December 3, 2010, which forms a part of the Registration Statement (the “Prospectus”), and as may be set forth in one or more supplements to the Prospectus. This opinion letter is rendered in connection with the issuance of up to $3,000,000 of common stock, $0.01 par value per share, of the Company (the “Shares”) from time to time as described in the Prospectus, and a prospectus supplement dated March 31, 2011 (the “Prospectus Supplement”). This opinion letter is rendered pursuant to Item 9.01 of Form 8-K and Item 6.01(b)(5) of Regulation S-K.

We are familiar with the proceedings taken by the Company with respect to the proposed issuance and sale of the Shares pursuant to the terms of a standby equity distribution agreement dated March 26, 2010 by and among the Company and YA Global Master SPV LTD. (the “Agreement”).

In connection therewith, we have relied also 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.

Based upon the foregoing, and having regard for such legal considerations as we have deemed relevant, we are of the opinion that the Shares have been duly authorized by the Company and, when issued and delivered by the Company against payment therefor in accordance with the Registration Statement and the related Prospectus and Prospectus Supplement and the Agreement, will be duly issued, fully paid and non-assessable.

We hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Company’s current report on Form 8-K, filed with the Securities and Exchange Commission, which is incorporated into the Registration Statement and to the references to McGrath North Mullin & Kratz, PC LLO under the caption “Legal Matters” in the Prospectus. 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 Securities and Exchange Commission.