<?xml version="1.0" encoding="US-ASCII"?>
<!--XBRL Document Created with WebFilings-->
<xsd:schema attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://redlion.rdln.com/20120331" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:nonnum="http://www.xbrl.org/dtr/type/non-numeric" xmlns:rlh="http://redlion.rdln.com/20120331" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
  <xsd:import namespace="http://fasb.org/us-gaap/2011-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2011/elts/us-gaap-2011-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-roles/2011-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2011/elts/us-roles-2011-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-types/2011-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2011/elts/us-types-2011-01-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2003/instance" schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2003/linkbase" schemaLocation="http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/arcrole/fact-explanatoryFact" schemaLocation="http://www.xbrl.org/lrr/arcrole/factExplanatory-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/role/negated" schemaLocation="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/role/net" schemaLocation="http://www.xbrl.org/lrr/role/net-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/dtr/type/non-numeric" schemaLocation="http://www.xbrl.org/dtr/type/nonNumeric-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/dtr/type/numeric" schemaLocation="http://www.xbrl.org/dtr/type/numeric-2009-12-16.xsd" />
  <xsd:import namespace="http://xbrl.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/country/2011-01-31" schemaLocation="http://xbrl.sec.gov/country/2011/country-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/currency/2011-01-31" schemaLocation="http://xbrl.sec.gov/currency/2011/currency-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/dei/2011-01-31" schemaLocation="http://xbrl.sec.gov/dei/2011/dei-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/exch/2011-01-31" schemaLocation="http://xbrl.sec.gov/exch/2011/exch-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/invest/2011-01-31" schemaLocation="http://xbrl.sec.gov/invest/2011/invest-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/naics/2011-01-31" schemaLocation="http://xbrl.sec.gov/naics/2011/naics-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/sic/2011-01-31" schemaLocation="http://xbrl.sec.gov/sic/2011/sic-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/stpr/2011-01-31" schemaLocation="http://xbrl.sec.gov/stpr/2011/stpr-2011-01-31.xsd" />
  <xsd:annotation>
    <xsd:appinfo>
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="rlh-20120331_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="rlh-20120331_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="rlh-20120331_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="rlh-20120331_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:type="simple" />
      <link:roleType id="AssetsHeldForSale" roleURI="http://redlion.rdln.com/role/AssetsHeldForSale">
        <link:definition>2107100 - Disclosure - Assets Held for Sale</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="BasisOfPresentation" roleURI="http://redlion.rdln.com/role/BasisOfPresentation">
        <link:definition>2102100 - Disclosure - Basis of Presentation</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="BusinessSegments" roleURI="http://redlion.rdln.com/role/BusinessSegments">
        <link:definition>2111100 - Disclosure - Business Segments</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingencies" roleURI="http://redlion.rdln.com/role/CommitmentsAndContingencies">
        <link:definition>2116100 - Disclosure - Commitments and Contingencies</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="ConsolidatedBalanceSheetsUnaudited" roleURI="http://redlion.rdln.com/role/ConsolidatedBalanceSheetsUnaudited">
        <link:definition>1001000 - Statement - Consolidated Balance Sheets (Unaudited)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="ConsolidatedBalanceSheetsUnauditedParenthetical" roleURI="http://redlion.rdln.com/role/ConsolidatedBalanceSheetsUnauditedParenthetical">
        <link:definition>1001501 - Statement - Consolidated Balance Sheets (Unaudited) (Parenthetical)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="ConsolidatedStatementsOfCashFlowsUnaudited" roleURI="http://redlion.rdln.com/role/ConsolidatedStatementsOfCashFlowsUnaudited">
        <link:definition>1003000 - Statement - Consolidated Statements of Cash Flows (Unaudited)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="ConsolidatedStatementsOfOperationsUnaudited" roleURI="http://redlion.rdln.com/role/ConsolidatedStatementsOfOperationsUnaudited">
        <link:definition>1002000 - Statement - Consolidated Statements of Operations (Unaudited)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="ConsolidatedStatementsOfOperationsUnauditedParenthetical" roleURI="http://redlion.rdln.com/role/ConsolidatedStatementsOfOperationsUnauditedParenthetical">
        <link:definition>1002501 - Statement - Consolidated Statements of Operations (Unaudited) (Parenthetical)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CreditFacilityAndLongTermDebt" roleURI="http://redlion.rdln.com/role/CreditFacilityAndLongTermDebt">
        <link:definition>2110100 - Disclosure - Credit Facility and Long Term Debt</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="DiscontinuedOperations" roleURI="http://redlion.rdln.com/role/DiscontinuedOperations">
        <link:definition>2108100 - Disclosure - Discontinued Operations</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="DocumentAndEntityInformation" roleURI="http://redlion.rdln.com/role/DocumentAndEntityInformation">
        <link:definition>0001000 - Document - Document and Entity Information</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="EarningsLossPerShare" roleURI="http://redlion.rdln.com/role/EarningsLossPerShare">
        <link:definition>2112100 - Disclosure - Earnings (Loss) Per Share</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="FairValueOfFinancialInstruments" roleURI="http://redlion.rdln.com/role/FairValueOfFinancialInstruments">
        <link:definition>2115100 - Disclosure - Fair Value of Financial Instruments</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="GoodwillAndIntangibles" roleURI="http://redlion.rdln.com/role/GoodwillAndIntangibles">
        <link:definition>2109100 - Disclosure - Goodwill and Intangibles</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxes" roleURI="http://redlion.rdln.com/role/IncomeTaxes">
        <link:definition>2113100 - Disclosure - Income Taxes</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="Liquidity" roleURI="http://redlion.rdln.com/role/Liquidity">
        <link:definition>2105100 - Disclosure - Liquidity</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="Organization" roleURI="http://redlion.rdln.com/role/Organization">
        <link:definition>2101100 - Disclosure - Organization</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="PropertyAndEquipment" roleURI="http://redlion.rdln.com/role/PropertyAndEquipment">
        <link:definition>2106100 - Disclosure - Property and Equipment</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="RecentAccountingPronouncements" roleURI="http://redlion.rdln.com/role/RecentAccountingPronouncements">
        <link:definition>2104100 - Disclosure - Recent Accounting Pronouncements</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensation" roleURI="http://redlion.rdln.com/role/StockBasedCompensation">
        <link:definition>2114100 - Disclosure - Stock Based Compensation</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
    </xsd:appinfo>
  </xsd:annotation>
  <xsd:element id="rlh_AssetImpairmentChargesIncludingDiscontinuedOperations" name="AssetImpairmentChargesIncludingDiscontinuedOperations" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="rlh_CashPaidDuringPeriodsForAbstract" name="CashPaidDuringPeriodsForAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="rlh_ConversionOfNonCurrentRestrictedCashToAccountsReceivable" name="ConversionOfNonCurrentRestrictedCashToAccountsReceivable" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="rlh_DisclosureOfAssetsHeldForSaleTextBlock" name="DisclosureOfAssetsHeldForSaleTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="rlh_DocumentAndEntityInformationAbstract" name="DocumentAndEntityInformationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="rlh_Entertainment" name="Entertainment" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="rlh_EntertainmentExpenses" name="EntertainmentExpenses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="rlh_HotelFacilityAndLandLease" name="HotelFacilityAndLandLease" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="rlh_IncomeLossBeforeTaxes" name="IncomeLossBeforeTaxes" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="rlh_LiquidityAbstract" name="LiquidityAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="rlh_LiquidityTextBlock" name="LiquidityTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="rlh_ReclassificationOfGoodwillToAssetsHeldForSale" name="ReclassificationOfGoodwillToAssetsHeldForSale" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="rlh_ReclassificationOfPropertyAndOtherAssetsToAssetsHeldForSale" name="ReclassificationOfPropertyAndOtherAssetsToAssetsHeldForSale" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
</xsd:schema>
