<?xml version="1.0" encoding="US-ASCII"?>
<!--XBRL Document Created with Wdesk from Workiva, formerly WebFilings-->
<!-- -->
<xsd:schema attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://www.cstbrands.com/20141231" xmlns:cst="http://www.cstbrands.com/20141231" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:nonnum="http://www.xbrl.org/dtr/type/non-numeric" xmlns:num="http://www.xbrl.org/dtr/type/numeric" xmlns:xbrldt="http://xbrl.org/2005/xbrldt" 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/2014-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2014/elts/us-gaap-2014-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-roles/2014-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2014/elts/us-roles-2014-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-types/2014-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2014/elts/us-types-2014-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/2013-01-31" schemaLocation="http://xbrl.sec.gov/country/2013/country-2013-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/currency/2014-01-31" schemaLocation="http://xbrl.sec.gov/currency/2014/currency-2014-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/dei/2014-01-31" schemaLocation="http://xbrl.sec.gov/dei/2014/dei-2014-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/exch/2014-01-31" schemaLocation="http://xbrl.sec.gov/exch/2014/exch-2014-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/invest/2013-01-31" schemaLocation="http://xbrl.sec.gov/invest/2013/invest-2013-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="cst-20141231_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="cst-20141231_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="cst-20141231_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="cst-20141231_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:type="simple" />
      <link:roleType id="AccruedExpensesAndOtherLongTermLiabilities" roleURI="http://www.cstbrands.com/role/AccruedExpensesAndOtherLongTermLiabilities">
        <link:definition>2134100 - Disclosure - Accrued Expenses and Other Long-Term Liabilities</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="AccruedExpensesAndOtherLongTermLiabilitiesAccruedExpensesDetails" roleURI="http://www.cstbrands.com/role/AccruedExpensesAndOtherLongTermLiabilitiesAccruedExpensesDetails">
        <link:definition>2434403 - Disclosure - Accrued Expenses and Other Long-Term Liabilities Accrued Expenses (Details)</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="AccruedExpensesAndOtherLongTermLiabilitiesAssetRetirementObligationsDetails" roleURI="http://www.cstbrands.com/role/AccruedExpensesAndOtherLongTermLiabilitiesAssetRetirementObligationsDetails">
        <link:definition>2434405 - Disclosure - Accrued Expenses and Other Long-Term Liabilities Asset Retirement Obligations (Details)</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="AccruedExpensesAndOtherLongTermLiabilitiesNarrativeDetails" roleURI="http://www.cstbrands.com/role/AccruedExpensesAndOtherLongTermLiabilitiesNarrativeDetails">
        <link:definition>2434402 - Disclosure - Accrued Expenses and Other Long-Term Liabilities - Narrative (Details)</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="AccruedExpensesAndOtherLongTermLiabilitiesOtherLongTermLiabilitiesDetails" roleURI="http://www.cstbrands.com/role/AccruedExpensesAndOtherLongTermLiabilitiesOtherLongTermLiabilitiesDetails">
        <link:definition>2434404 - Disclosure - Accrued Expenses and Other Long-Term Liabilities Other Long-Term Liabilities (Details)</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="AccruedExpensesAndOtherLongTermLiabilitiesTables" roleURI="http://www.cstbrands.com/role/AccruedExpensesAndOtherLongTermLiabilitiesTables">
        <link:definition>2334301 - Disclosure - Accrued Expenses and Other Long-Term Liabilities (Tables)</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="Acquisitions" roleURI="http://www.cstbrands.com/role/Acquisitions">
        <link:definition>2107100 - Disclosure - Acquisitions</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="AcquisitionsCrossamericaAcquisitionBalanceSheetDetails" roleURI="http://www.cstbrands.com/role/AcquisitionsCrossamericaAcquisitionBalanceSheetDetails">
        <link:definition>2407403 - Disclosure - Acquisitions CrossAmerica Acquisition Balance Sheet (Details)</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="AcquisitionsNarrativeDetails" roleURI="http://www.cstbrands.com/role/AcquisitionsNarrativeDetails">
        <link:definition>2407402 - Disclosure - Acquisitions Narrative (Details)</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="AcquisitionsSubsequentEventDetails" roleURI="http://www.cstbrands.com/role/AcquisitionsSubsequentEventDetails">
        <link:definition>2407404 - Disclosure - Acquisitions - Subsequent Event (Details)</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="AcquisitionsTables" roleURI="http://www.cstbrands.com/role/AcquisitionsTables">
        <link:definition>2307301 - Disclosure - Acquisitions (Tables)</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="AssetImpairments" roleURI="http://www.cstbrands.com/role/AssetImpairments">
        <link:definition>2110100 - Disclosure - Asset Impairments</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="AssetImpairmentsDetails" roleURI="http://www.cstbrands.com/role/AssetImpairmentsDetails">
        <link:definition>2410401 - Disclosure - Asset Impairments (Details)</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://www.cstbrands.com/role/CommitmentsAndContingencies">
        <link:definition>2143100 - 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="CommitmentsAndContingenciesMinimumCapitalLeasePaymentsDetails" roleURI="http://www.cstbrands.com/role/CommitmentsAndContingenciesMinimumCapitalLeasePaymentsDetails">
        <link:definition>2443404 - Disclosure - Commitments and Contingencies - Minimum Capital Lease Payments (Details)</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="CommitmentsAndContingenciesMinimumOperatingLeasePaymentsDetails" roleURI="http://www.cstbrands.com/role/CommitmentsAndContingenciesMinimumOperatingLeasePaymentsDetails">
        <link:definition>2443403 - Disclosure - Commitments and Contingencies - Minimum Operating Lease Payments (Details)</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="CommitmentsAndContingenciesNarrativeDetails" roleURI="http://www.cstbrands.com/role/CommitmentsAndContingenciesNarrativeDetails">
        <link:definition>2443402 - Disclosure - Commitments and Contingencies - Narrative (Details)</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="CommitmentsAndContingenciesRentalExpenseDetails" roleURI="http://www.cstbrands.com/role/CommitmentsAndContingenciesRentalExpenseDetails">
        <link:definition>2443405 - Disclosure - Commitments and Contingencies - Rental Expense (Details)</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="CommitmentsAndContingenciesTables" roleURI="http://www.cstbrands.com/role/CommitmentsAndContingenciesTables">
        <link:definition>2343301 - Disclosure - Commitments and Contingencies (Tables)</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="ConsolidatedAndCombinedStatementOfCashFlows" roleURI="http://www.cstbrands.com/role/ConsolidatedAndCombinedStatementOfCashFlows">
        <link:definition>1004000 - Statement - Consolidated and Combined Statement of Cash Flows</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="ConsolidatedAndCombinedStatementsOfChangesInShareholdersEquityNetInvestment" roleURI="http://www.cstbrands.com/role/ConsolidatedAndCombinedStatementsOfChangesInShareholdersEquityNetInvestment">
        <link:definition>1005000 - Statement - Consolidated and Combined Statements of Changes in Shareholders' Equity/ Net Investment</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="ConsolidatedAndCombinedStatementsOfComprehensiveIncomeStatement" roleURI="http://www.cstbrands.com/role/ConsolidatedAndCombinedStatementsOfComprehensiveIncomeStatement">
        <link:definition>1003000 - Statement - Consolidated and Combined Statements of Comprehensive Income Statement</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="ConsolidatedAndCombinedStatementsOfIncome" roleURI="http://www.cstbrands.com/role/ConsolidatedAndCombinedStatementsOfIncome">
        <link:definition>1002000 - Statement - Consolidated and Combined Statements of Income</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="ConsolidatedBalanceSheet" roleURI="http://www.cstbrands.com/role/ConsolidatedBalanceSheet">
        <link:definition>1001000 - Statement - Consolidated Balance Sheet</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="ConsolidatedBalanceSheetParenthetical" roleURI="http://www.cstbrands.com/role/ConsolidatedBalanceSheetParenthetical">
        <link:definition>1001001 - Statement - Consolidated Balance Sheet (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="Debt" roleURI="http://www.cstbrands.com/role/Debt">
        <link:definition>2137100 - Disclosure - 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="DebtAmendmentToCreditFacilityNarrativeDetails" roleURI="http://www.cstbrands.com/role/DebtAmendmentToCreditFacilityNarrativeDetails">
        <link:definition>2437402 - Disclosure - Debt - Amendment to Credit Facility - Narrative (Details)</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="DebtCreditFacilitiesNarrativeDetails" roleURI="http://www.cstbrands.com/role/DebtCreditFacilitiesNarrativeDetails">
        <link:definition>2437407 - Disclosure - Debt - Credit Facilities - Narrative (Details)</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="DebtCrossamericaCreditFacilityDetails" roleURI="http://www.cstbrands.com/role/DebtCrossamericaCreditFacilityDetails">
        <link:definition>2437408 - Disclosure - Debt - CrossAmerica Credit Facility (Details)</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="DebtCrossamericaOtherDebtDetails" roleURI="http://www.cstbrands.com/role/DebtCrossamericaOtherDebtDetails">
        <link:definition>2437409 - Disclosure - Debt - CrossAmerica Other Debt (Details)</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="DebtLineOfCreditFacilityDetails" roleURI="http://www.cstbrands.com/role/DebtLineOfCreditFacilityDetails">
        <link:definition>2437406 - Disclosure - Debt - Line of Credit Facility (Details)</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="DebtLongTermDebtDetails" roleURI="http://www.cstbrands.com/role/DebtLongTermDebtDetails">
        <link:definition>2437404 - Disclosure - Debt - Long-Term Debt (Details)</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="DebtMaturitiesOfLongTermDebtDetails" roleURI="http://www.cstbrands.com/role/DebtMaturitiesOfLongTermDebtDetails">
        <link:definition>2437405 - Disclosure - Debt Maturities of Long-Term Debt (Details)</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="DebtNotesNarrativeDetails" roleURI="http://www.cstbrands.com/role/DebtNotesNarrativeDetails">
        <link:definition>2437403 - Disclosure - Debt - Notes Narrative (Details)</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="DebtTables" roleURI="http://www.cstbrands.com/role/DebtTables">
        <link:definition>2337301 - Disclosure - Debt (Tables)</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="DeiInformationDocument" roleURI="http://www.cstbrands.com/role/DeiInformationDocument">
        <link:definition>0001000 - Document - DEI Information Document</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="DescriptionOfBusinessBasisOfPresentationConcentrationRiskAndOtherItemsAffectingOurBusiness" roleURI="http://www.cstbrands.com/role/DescriptionOfBusinessBasisOfPresentationConcentrationRiskAndOtherItemsAffectingOurBusiness">
        <link:definition>2101100 - Disclosure - Description of Business, Basis of Presentation, Concentration Risk and Other Items Affecting Our Business</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="DescriptionOfBusinessBasisOfPresentationConcentrationRiskAndOtherItemsAffectingOurBusinessNarrativeDetails" roleURI="http://www.cstbrands.com/role/DescriptionOfBusinessBasisOfPresentationConcentrationRiskAndOtherItemsAffectingOurBusinessNarrativeDetails">
        <link:definition>2401401 - Disclosure - Description of Business, Basis of Presentation, Concentration Risk and Other Items Affecting Our Business - Narrative (Details)</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="DescriptionOfBusinessBasisOfPresentationConcentrationRiskAndOtherItemsAffectingOurBusinessSubsequentEventDetails" roleURI="http://www.cstbrands.com/role/DescriptionOfBusinessBasisOfPresentationConcentrationRiskAndOtherItemsAffectingOurBusinessSubsequentEventDetails">
        <link:definition>2401402 - Disclosure - Description of Business, Basis of Presentation, Concentration Risk and Other Items Affecting Our Business - Subsequent event (Details)</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="EarningsPerShare" roleURI="http://www.cstbrands.com/role/EarningsPerShare">
        <link:definition>2152100 - Disclosure - Earnings 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="EarningsPerShareAntidilutiveSecuritiesExcludedFromComputationOfEarningsPerShareDetails" roleURI="http://www.cstbrands.com/role/EarningsPerShareAntidilutiveSecuritiesExcludedFromComputationOfEarningsPerShareDetails">
        <link:definition>2452405 - Disclosure - Earnings Per Share - Antidilutive Securities Excluded from Computation of Earnings Per Share (Details)</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="EarningsPerShareEarningsPerShareBasicDetails" roleURI="http://www.cstbrands.com/role/EarningsPerShareEarningsPerShareBasicDetails">
        <link:definition>2452403 - Disclosure - Earnings Per Share - Earnings Per Share Basic (Details)</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="EarningsPerShareEarningsPerShareDilutedDetails" roleURI="http://www.cstbrands.com/role/EarningsPerShareEarningsPerShareDilutedDetails">
        <link:definition>2452404 - Disclosure - Earnings Per Share Earnings per Share Diluted (Details)</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="EarningsPerShareNarrativeDetails" roleURI="http://www.cstbrands.com/role/EarningsPerShareNarrativeDetails">
        <link:definition>2452402 - Disclosure - Earnings Per Share - Narrative (Details)</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="EarningsPerShareTables" roleURI="http://www.cstbrands.com/role/EarningsPerShareTables">
        <link:definition>2352301 - Disclosure - Earnings Per Share (Tables)</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="EmployeeBenefitPlans" roleURI="http://www.cstbrands.com/role/EmployeeBenefitPlans">
        <link:definition>2158100 - Disclosure - Employee Benefit Plans</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="EmployeeBenefitPlansDefinedContributionPlansDetails" roleURI="http://www.cstbrands.com/role/EmployeeBenefitPlansDefinedContributionPlansDetails">
        <link:definition>2458403 - Disclosure - Employee Benefit Plans - Defined Contribution Plans (Details)</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="EmployeeBenefitPlansNarrativeDetails" roleURI="http://www.cstbrands.com/role/EmployeeBenefitPlansNarrativeDetails">
        <link:definition>2458402 - Disclosure - Employee Benefit Plans - Narrative (Details)</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="EmployeeBenefitPlansTables" roleURI="http://www.cstbrands.com/role/EmployeeBenefitPlansTables">
        <link:definition>2358301 - Disclosure - Employee Benefit Plans (Tables)</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="Equity" roleURI="http://www.cstbrands.com/role/Equity">
        <link:definition>2146100 - Disclosure - Equity</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="EquityCstCommonStockAndTreasuryStockActivityDetails" roleURI="http://www.cstbrands.com/role/EquityCstCommonStockAndTreasuryStockActivityDetails">
        <link:definition>2446404 - Disclosure - Equity - CST Common Stock and Treasury Stock Activity (Details)</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="EquityDividendActivityDetails" roleURI="http://www.cstbrands.com/role/EquityDividendActivityDetails">
        <link:definition>2446403 - Disclosure - Equity - Dividend Activity (Details)</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="EquityNarrativeDetails" roleURI="http://www.cstbrands.com/role/EquityNarrativeDetails">
        <link:definition>2446402 - Disclosure - Equity - Narrative (Details)</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="EquityOtherComprehensiveIncomeDetails" roleURI="http://www.cstbrands.com/role/EquityOtherComprehensiveIncomeDetails">
        <link:definition>2446405 - Disclosure - Equity - Other Comprehensive Income (Details)</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="EquityTables" roleURI="http://www.cstbrands.com/role/EquityTables">
        <link:definition>2346301 - Disclosure - Equity (Tables)</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="FairValueMeasurements" roleURI="http://www.cstbrands.com/role/FairValueMeasurements">
        <link:definition>2113100 - Disclosure - Fair Value Measurements</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="FairValueMeasurementsDetails" roleURI="http://www.cstbrands.com/role/FairValueMeasurementsDetails">
        <link:definition>2413402 - Disclosure - Fair Value Measurements (Details)</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="FairValueMeasurementsTables" roleURI="http://www.cstbrands.com/role/FairValueMeasurementsTables">
        <link:definition>2313301 - Disclosure - Fair Value Measurements (Tables)</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="Goodwill" roleURI="http://www.cstbrands.com/role/Goodwill">
        <link:definition>2128100 - Disclosure - Goodwill</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="GoodwillDetails" roleURI="http://www.cstbrands.com/role/GoodwillDetails">
        <link:definition>2428403 - Disclosure - Goodwill (Details)</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="GoodwillNarrativeDetails" roleURI="http://www.cstbrands.com/role/GoodwillNarrativeDetails">
        <link:definition>2428402 - Disclosure - Goodwill - Narrative (Details)</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="GoodwillTables" roleURI="http://www.cstbrands.com/role/GoodwillTables">
        <link:definition>2328301 - Disclosure - Goodwill (Tables)</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="GuarantorSubsidiariesConsolidatingBalanceSheetsDetails" roleURI="http://www.cstbrands.com/role/GuarantorSubsidiariesConsolidatingBalanceSheetsDetails">
        <link:definition>2468403 - Disclosure - Guarantor Subsidiaries - Consolidating Balance Sheets (Details)</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="GuarantorSubsidiariesConsolidatingBalanceSheetsDetailsCalc2" roleURI="http://www.cstbrands.com/role/GuarantorSubsidiariesConsolidatingBalanceSheetsDetailsCalc2">
        <link:definition>2468403 - Disclosure - Guarantor Subsidiaries - Consolidating Balance Sheets (Details)</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="GuarantorSubsidiariesConsolidatingIncomeStatementsDetails" roleURI="http://www.cstbrands.com/role/GuarantorSubsidiariesConsolidatingIncomeStatementsDetails">
        <link:definition>2468404 - Disclosure - Guarantor Subsidiaries - Consolidating Income Statements (Details)</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="GuarantorSubsidiariesConsolidatingStatementsOfCashFlowsDetails" roleURI="http://www.cstbrands.com/role/GuarantorSubsidiariesConsolidatingStatementsOfCashFlowsDetails">
        <link:definition>2468405 - Disclosure - Guarantor Subsidiaries - Consolidating Statements of Cash Flows (Details)</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="GuarantorSubsidiariesNarrativeDetails" roleURI="http://www.cstbrands.com/role/GuarantorSubsidiariesNarrativeDetails">
        <link:definition>2468402 - Disclosure - Guarantor Subsidiaries - Narrative (Details)</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="GuarantorSubsidiariesNotes" roleURI="http://www.cstbrands.com/role/GuarantorSubsidiariesNotes">
        <link:definition>2168100 - Disclosure - Guarantor Subsidiaries (Notes)</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="GuarantorSubsidiariesTables" roleURI="http://www.cstbrands.com/role/GuarantorSubsidiariesTables">
        <link:definition>2368301 - Disclosure - Guarantor Subsidiaries (Tables)</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://www.cstbrands.com/role/IncomeTaxes">
        <link:definition>2155100 - 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="IncomeTaxesComponentsOfIncomeTaxExpenseDetails" roleURI="http://www.cstbrands.com/role/IncomeTaxesComponentsOfIncomeTaxExpenseDetails">
        <link:definition>2455405 - Disclosure - Income Taxes - Components of Income Tax Expense (Details)</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="IncomeTaxesIncomeBeforeIncomeTaxExpenseDetails" roleURI="http://www.cstbrands.com/role/IncomeTaxesIncomeBeforeIncomeTaxExpenseDetails">
        <link:definition>2455403 - Disclosure - Income Taxes - Income Before Income Tax Expense (Details)</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="IncomeTaxesNarrativeDetails" roleURI="http://www.cstbrands.com/role/IncomeTaxesNarrativeDetails">
        <link:definition>2455402 - Disclosure - Income Taxes - Narrative (Details)</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="IncomeTaxesReconciliationOfUSFederalIncomeTaxRateDetails" roleURI="http://www.cstbrands.com/role/IncomeTaxesReconciliationOfUSFederalIncomeTaxRateDetails">
        <link:definition>2455404 - Disclosure - Income Taxes - Reconciliation of U.S. Federal Income Tax Rate (Details)</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="IncomeTaxesTables" roleURI="http://www.cstbrands.com/role/IncomeTaxesTables">
        <link:definition>2355301 - Disclosure - Income Taxes (Tables)</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="IncomeTaxesTaxEffectsOfSignificantTemporaryDifferencesDetails" roleURI="http://www.cstbrands.com/role/IncomeTaxesTaxEffectsOfSignificantTemporaryDifferencesDetails">
        <link:definition>2455406 - Disclosure - Income Taxes - Tax Effects of Significant Temporary Differences (Details)</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="IntangibleAssets" roleURI="http://www.cstbrands.com/role/IntangibleAssets">
        <link:definition>2131100 - Disclosure - Intangible Assets</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="IntangibleAssetsIntangibleAssetsDetails" roleURI="http://www.cstbrands.com/role/IntangibleAssetsIntangibleAssetsDetails">
        <link:definition>2431403 - Disclosure - Intangible Assets - Intangible Assets (Details)</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="IntangibleAssetsNarrativeDetails" roleURI="http://www.cstbrands.com/role/IntangibleAssetsNarrativeDetails">
        <link:definition>2431402 - Disclosure - Intangible Assets - Narrative (Details)</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="IntangibleAssetsTables" roleURI="http://www.cstbrands.com/role/IntangibleAssetsTables">
        <link:definition>2331301 - Disclosure - Intangible Assets (Tables)</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="Inventories" roleURI="http://www.cstbrands.com/role/Inventories">
        <link:definition>2119100 - Disclosure - Inventories</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="InventoriesDetails" roleURI="http://www.cstbrands.com/role/InventoriesDetails">
        <link:definition>2419403 - Disclosure - Inventories (Details)</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="InventoriesNarrativeDetails" roleURI="http://www.cstbrands.com/role/InventoriesNarrativeDetails">
        <link:definition>2419402 - Disclosure - Inventories - Narrative (Details)</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="InventoriesTables" roleURI="http://www.cstbrands.com/role/InventoriesTables">
        <link:definition>2319301 - Disclosure - Inventories (Tables)</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="NetworkOptimization" roleURI="http://www.cstbrands.com/role/NetworkOptimization">
        <link:definition>2122100 - Disclosure - Network Optimization</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="NetworkOptimizationDetails" roleURI="http://www.cstbrands.com/role/NetworkOptimizationDetails">
        <link:definition>2422402 - Disclosure - Network Optimization (Details)</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="NetworkOptimizationNarrativeDetails" roleURI="http://www.cstbrands.com/role/NetworkOptimizationNarrativeDetails">
        <link:definition>2422403 - Disclosure - Network Optimization - Narrative (Details)</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="NetworkOptimizationTables" roleURI="http://www.cstbrands.com/role/NetworkOptimizationTables">
        <link:definition>2322301 - Disclosure - Network Optimization (Tables)</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://www.cstbrands.com/role/PropertyAndEquipment">
        <link:definition>2125100 - 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="PropertyAndEquipmentDetails" roleURI="http://www.cstbrands.com/role/PropertyAndEquipmentDetails">
        <link:definition>2425403 - Disclosure - Property and Equipment (Details)</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="PropertyAndEquipmentNarrativeDetails" roleURI="http://www.cstbrands.com/role/PropertyAndEquipmentNarrativeDetails">
        <link:definition>2425402 - Disclosure - Property and Equipment - Narrative (Details)</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="PropertyAndEquipmentTables" roleURI="http://www.cstbrands.com/role/PropertyAndEquipmentTables">
        <link:definition>2325301 - Disclosure - Property and Equipment (Tables)</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="QuarterlyFinancialData" roleURI="http://www.cstbrands.com/role/QuarterlyFinancialData">
        <link:definition>2167100 - Disclosure - Quarterly Financial Data</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="QuarterlyFinancialDataNarrativeDetails" roleURI="http://www.cstbrands.com/role/QuarterlyFinancialDataNarrativeDetails">
        <link:definition>2467402 - Disclosure - Quarterly Financial Data - Narrative (Details)</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="QuarterlyFinancialDataQuarterlyInformationDetails" roleURI="http://www.cstbrands.com/role/QuarterlyFinancialDataQuarterlyInformationDetails">
        <link:definition>2467403 - Disclosure - Quarterly Financial Data - Quarterly Information (Details)</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="QuarterlyFinancialDataTables" roleURI="http://www.cstbrands.com/role/QuarterlyFinancialDataTables">
        <link:definition>2367301 - Disclosure - Quarterly Financial Data (Tables)</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="ReceivablesAllowanceForDoubtfulAccountsDetails" roleURI="http://www.cstbrands.com/role/ReceivablesAllowanceForDoubtfulAccountsDetails">
        <link:definition>2416403 - Disclosure - Receivables - Allowance for Doubtful Accounts (Details)</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="ReceivablesNotes" roleURI="http://www.cstbrands.com/role/ReceivablesNotes">
        <link:definition>2116100 - Disclosure - Receivables (Notes)</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="ReceivablesReceivablesDetails" roleURI="http://www.cstbrands.com/role/ReceivablesReceivablesDetails">
        <link:definition>2416402 - Disclosure - Receivables - Receivables (Details)</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="ReceivablesTables" roleURI="http://www.cstbrands.com/role/ReceivablesTables">
        <link:definition>2316301 - Disclosure - Receivables (Tables)</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="RelatedParty" roleURI="http://www.cstbrands.com/role/RelatedParty">
        <link:definition>2140100 - Disclosure - Related Party</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="RelatedPartyActivityWithValeroDetails" roleURI="http://www.cstbrands.com/role/RelatedPartyActivityWithValeroDetails">
        <link:definition>2440403 - Disclosure - Related Party - Activity with Valero (Details)</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="RelatedPartyNarrativeDetails" roleURI="http://www.cstbrands.com/role/RelatedPartyNarrativeDetails">
        <link:definition>2440402 - Disclosure - Related Party - Narrative (Details)</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="RelatedPartyReconciliationOfNetTransfersToValeroDetails" roleURI="http://www.cstbrands.com/role/RelatedPartyReconciliationOfNetTransfersToValeroDetails">
        <link:definition>2440404 - Disclosure - Related Party - Reconciliation of Net Transfers to Valero (Details)</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="RelatedPartyTables" roleURI="http://www.cstbrands.com/role/RelatedPartyTables">
        <link:definition>2340301 - Disclosure - Related Party (Tables)</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="SegmentInformation" roleURI="http://www.cstbrands.com/role/SegmentInformation">
        <link:definition>2161100 - Disclosure - Segment 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="SegmentInformationLongLivedAssetsByReportableSegmentDetails" roleURI="http://www.cstbrands.com/role/SegmentInformationLongLivedAssetsByReportableSegmentDetails">
        <link:definition>2461405 - Disclosure - Segment Information - Long-Lived Assets by Reportable Segment (Details)</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="SegmentInformationNarrativeDetails" roleURI="http://www.cstbrands.com/role/SegmentInformationNarrativeDetails">
        <link:definition>2461402 - Disclosure - Segment Information - Narrative (Details)</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="SegmentInformationReportableSegments" roleURI="http://www.cstbrands.com/role/SegmentInformationReportableSegments">
        <link:definition>2461403 - Disclosure - Segment Information - Reportable 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="SegmentInformationRevenueByProductDetails" roleURI="http://www.cstbrands.com/role/SegmentInformationRevenueByProductDetails">
        <link:definition>2461404 - Disclosure - Segment Information - Revenue by Product (Details)</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="SegmentInformationTables" roleURI="http://www.cstbrands.com/role/SegmentInformationTables">
        <link:definition>2361301 - Disclosure - Segment Information (Tables)</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="SegmentInformationTotalAssetsByReportingSegmentDetails" roleURI="http://www.cstbrands.com/role/SegmentInformationTotalAssetsByReportingSegmentDetails">
        <link:definition>2461406 - Disclosure - Segment Information - Total Assets by Reporting Segment (Details)</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="SignificantAccountingPolicies" roleURI="http://www.cstbrands.com/role/SignificantAccountingPolicies">
        <link:definition>2104100 - Disclosure - Significant Accounting Policies</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="SignificantAccountingPoliciesNarrativeDetails" roleURI="http://www.cstbrands.com/role/SignificantAccountingPoliciesNarrativeDetails">
        <link:definition>2404402 - Disclosure - Significant Accounting Policies - Narrative (Details)</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="SignificantAccountingPoliciesPolicies" roleURI="http://www.cstbrands.com/role/SignificantAccountingPoliciesPolicies">
        <link:definition>2204201 - Disclosure - Significant Accounting Policies (Policies)</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://www.cstbrands.com/role/StockBasedCompensation">
        <link:definition>2149100 - 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>
      <link:roleType id="StockBasedCompensationCrossamericaEquityBasedAwardsActivityDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationCrossamericaEquityBasedAwardsActivityDetails">
        <link:definition>2449412 - Disclosure - Stock-Based Compensation - CrossAmerica equity-based awards activity (Details)</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="StockBasedCompensationCrossamericaEquityBasedAwardsDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationCrossamericaEquityBasedAwardsDetails">
        <link:definition>2449411 - Disclosure - Stock-Based Compensation - CrossAmerica equity-based awards (Details)</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="StockBasedCompensationFairValueInputsDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationFairValueInputsDetails">
        <link:definition>2449406 - Disclosure - Stock-Based Compensation - Fair Value Inputs (Details)</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="StockBasedCompensationNarrativeDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationNarrativeDetails">
        <link:definition>2449402 - Disclosure - Stock-Based Compensation - Narrative (Details)</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="StockBasedCompensationRestrictedShareActivityDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationRestrictedShareActivityDetails">
        <link:definition>2449408 - Disclosure - Stock-Based Compensation - Restricted share activity (Details)</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="StockBasedCompensationRestrictedSharesDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationRestrictedSharesDetails">
        <link:definition>2449407 - Disclosure - Stock-Based Compensation - Restricted shares (Details)</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="StockBasedCompensationRestrictedStockUnitsActivityDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationRestrictedStockUnitsActivityDetails">
        <link:definition>2449410 - Disclosure - Stock-Based Compensation - Restricted stock units activity (Details)</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="StockBasedCompensationRestrictedStockUnitsDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationRestrictedStockUnitsDetails">
        <link:definition>2449409 - Disclosure - Stock-Based Compensation - Restricted stock units (Details)</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="StockBasedCompensationStockBasedCompensationExpenseDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationStockBasedCompensationExpenseDetails">
        <link:definition>2449403 - Disclosure - Stock-Based Compensation - Stock-Based Compensation Expense (Details)</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="StockBasedCompensationStockOptionActivityDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationStockOptionActivityDetails">
        <link:definition>2449405 - Disclosure - Stock-Based Compensation - Stock Option Activity (Details)</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="StockBasedCompensationStockOptionsDetails" roleURI="http://www.cstbrands.com/role/StockBasedCompensationStockOptionsDetails">
        <link:definition>2449404 - Disclosure - Stock-Based Compensation - Stock Options (Details)</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="StockBasedCompensationTables" roleURI="http://www.cstbrands.com/role/StockBasedCompensationTables">
        <link:definition>2349301 - Disclosure - Stock-Based Compensation (Tables)</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="SupplementalCashFlowInformation" roleURI="http://www.cstbrands.com/role/SupplementalCashFlowInformation">
        <link:definition>2164100 - Disclosure - Supplemental Cash Flow 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="SupplementalCashFlowInformationChangesInCurrentAssetsAndLiabilitiesDetails" roleURI="http://www.cstbrands.com/role/SupplementalCashFlowInformationChangesInCurrentAssetsAndLiabilitiesDetails">
        <link:definition>2464403 - Disclosure - Supplemental Cash Flow Information - Changes in Current Assets and Liabilities (Details)</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="SupplementalCashFlowInformationInterestAndTaxesPaidDetails" roleURI="http://www.cstbrands.com/role/SupplementalCashFlowInformationInterestAndTaxesPaidDetails">
        <link:definition>2464404 - Disclosure - Supplemental Cash Flow Information - Interest and Taxes Paid (Details)</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="SupplementalCashFlowInformationNarrativeDetails" roleURI="http://www.cstbrands.com/role/SupplementalCashFlowInformationNarrativeDetails">
        <link:definition>2464402 - Disclosure - Supplemental Cash Flow Information - Narrative (Details)</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="SupplementalCashFlowInformationTables" roleURI="http://www.cstbrands.com/role/SupplementalCashFlowInformationTables">
        <link:definition>2364301 - Disclosure - Supplemental Cash Flow Information (Tables)</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 abstract="true" id="cst_A10yearlifeMember" name="A10yearlifeMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_A15yearlifeMember" name="A15yearlifeMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_A5yearlifeCovenantsMember" name="A5yearlifeCovenantsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_A5yearlifeaboveandbelowmarketleasesMember" name="A5yearlifeaboveandbelowmarketleasesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_AcquisitionofEricksonOilProductsMember" name="AcquisitionofEricksonOilProductsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_AcquisitionofLandmarkIndustriesStoresMember" name="AcquisitionofLandmarkIndustriesStoresMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_AcquisitionofNiceNEasyMember" name="AcquisitionofNiceNEasyMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_AcquisitionsAbstract" name="AcquisitionsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_AdjustmenttoAdditionalPaidinCapitalfromNetParentInvestment" name="AdjustmenttoAdditionalPaidinCapitalfromNetParentInvestment" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_AlternateBaseRateMember" name="AlternateBaseRateMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_AmountdueeachofthenextfiveyearsMember" name="AmountdueeachofthenextfiveyearsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_AssetSaleMember" name="AssetSaleMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_AssetsIdentifiedasPossibleFutureForSaleMember" name="AssetsIdentifiedasPossibleFutureForSaleMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_AustinMember" name="AustinMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_BusinessCombinationincreasedecreaseinallowanceforaccountreceivable" name="BusinessCombinationincreasedecreaseinallowanceforaccountreceivable" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_CSTBrandsInc.Member" name="CSTBrandsInc.Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_CSTDefinedContributionPlanMember" name="CSTDefinedContributionPlanMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_CSTStandaloneMember" name="CSTStandaloneMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_CapitalExpenditures" name="CapitalExpenditures" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_ChangeOfControlMember" name="ChangeOfControlMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_CommonunitsMember" name="CommonunitsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_ConsolidatedFixedChargeCoverageRatio" name="ConsolidatedFixedChargeCoverageRatio" nillable="true" substitutionGroup="xbrli:item" type="xbrli:pureItemType" xbrli:periodType="instant" />
  <xsd:element id="cst_ConsolidatedLeaseAdjustedLeverageRatio" name="ConsolidatedLeaseAdjustedLeverageRatio" nillable="true" substitutionGroup="xbrli:item" type="xbrli:pureItemType" xbrli:periodType="instant" />
  <xsd:element id="cst_ContractMargin" name="ContractMargin" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="cst_ContributionsFromDistributionsToValeroNet" name="ContributionsFromDistributionsToValeroNet" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="cst_CostOfSalesVendorAllowancesAccruedRebates" name="CostOfSalesVendorAllowancesAccruedRebates" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_CrossAmericaMember" name="CrossAmericaMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_DebtInstrumentCovenantConsolidatedFixedChargeCoverageRatioMinimum" name="DebtInstrumentCovenantConsolidatedFixedChargeCoverageRatioMinimum" nillable="true" substitutionGroup="xbrli:item" type="xbrli:pureItemType" xbrli:periodType="instant" />
  <xsd:element id="cst_DebtInstrumentCovenantLeaseAdjustedLeverageRatioMaximum" name="DebtInstrumentCovenantLeaseAdjustedLeverageRatioMaximum" nillable="true" substitutionGroup="xbrli:item" type="xbrli:pureItemType" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="cst_DebtInstrumentRedemptionRequirementsByCriteriaAxis" name="DebtInstrumentRedemptionRequirementsByCriteriaAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_DebtInterestOptionsAxis" name="DebtInterestOptionsAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_DebtInterestOptionsDomain" name="DebtInterestOptionsDomain" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_DebtcompliancetimingAxis" name="DebtcompliancetimingAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_DebtcompliancetimingDomain" name="DebtcompliancetimingDomain" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_DefinedContributionPlanProfitSharingPercent" name="DefinedContributionPlanProfitSharingPercent" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_DocumentandEntityInformationAbstract" name="DocumentandEntityInformationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_FairValueAdjustmentfromAcquisitionMember" name="FairValueAdjustmentfromAcquisitionMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_FirstOptionMember" name="FirstOptionMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_GuarantorNarrativeAbstract" name="GuarantorNarrativeAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_ImmediatevestingMember" name="ImmediatevestingMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_Incrementalcommonsharesattributabletoparticipatingnonvestedshareswithnonforfeitabledividendrightsrestrictedstock" name="Incrementalcommonsharesattributabletoparticipatingnonvestedshareswithnonforfeitabledividendrightsrestrictedstock" nillable="true" substitutionGroup="xbrli:item" type="xbrli:sharesItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_Incrementalcommonsharesattributabletoparticipatingnonvestedshareswithnonforfeitabledividendrightsrestrictedstockunits" name="Incrementalcommonsharesattributabletoparticipatingnonvestedshareswithnonforfeitabledividendrightsrestrictedstockunits" nillable="true" substitutionGroup="xbrli:item" type="xbrli:sharesItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_IntercompanyLiabilities" name="IntercompanyLiabilities" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="cst_InterestSpreadAxis" name="InterestSpreadAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_InterestSpreadDomain" name="InterestSpreadDomain" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_LeaseRate" name="LeaseRate" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_LineOfCreditFacilityFinancialCovenantsCombinedInterestChargeCoverageRatio" name="LineOfCreditFacilityFinancialCovenantsCombinedInterestChargeCoverageRatio" nillable="true" substitutionGroup="xbrli:item" type="xbrli:pureItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_LineOfCreditFacilityFinancialCovenantsCombinedLeverageRatio" name="LineOfCreditFacilityFinancialCovenantsCombinedLeverageRatio" nillable="true" substitutionGroup="xbrli:item" type="xbrli:pureItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_MerchandiseSalesMember" name="MerchandiseSalesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_MotorFuelSalesMember" name="MotorFuelSalesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_MotorFuelTaxesPolicyPolicyTextBlock" name="MotorFuelTaxesPolicyPolicyTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_NetParentInvestmentMember" name="NetParentInvestmentMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_NetTransfersFromToValero" name="NetTransfersFromToValero" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="cst_NettransferofasstsandliabilitiesRelatedParty" name="NettransferofasstsandliabilitiesRelatedParty" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_OtherProductRevenuesMember" name="OtherProductRevenuesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_PaymentforacquisitionofGeneralPartnerownershipandIncentiveDistributionRights" name="PaymentforacquisitionofGeneralPartnerownershipandIncentiveDistributionRights" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_QuarterlyMember" name="QuarterlyMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_ReconciliationOfNetChangeInNetParentCompanyInvestmentTableTextBlock" name="ReconciliationOfNetChangeInNetParentCompanyInvestmentTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_RevolvingCreditFacilitysMaximumLeverageRatioConstraint" name="RevolvingCreditFacilitysMaximumLeverageRatioConstraint" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="cst_SaleLeasebackTransactionMember" name="SaleLeasebackTransactionMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_SaleofheldforsaleassetsMember" name="SaleofheldforsaleassetsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_SanAntonioMember" name="SanAntonioMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_SecondOptionMember" name="SecondOptionMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_SecurityInterestsInCapitalStockOfDomesticSubsidiaries" name="SecurityInterestsInCapitalStockOfDomesticSubsidiaries" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element id="cst_SecurityInterestsInNonVotingEquityInterestsOfForeignSubsidiaries" name="SecurityInterestsInNonVotingEquityInterestsOfForeignSubsidiaries" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element id="cst_SecurityInterestsInVotingEquityInterestsOfForeignSubsidiaries" name="SecurityInterestsInVotingEquityInterestsOfForeignSubsidiaries" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element id="cst_SharebasedCompensationforServicesProvidedPriortoLegalSeparation" name="SharebasedCompensationforServicesProvidedPriortoLegalSeparation" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="cst_SpinoffTransactionOwnershipPercentageRetainedbyParentCompany" name="SpinoffTransactionOwnershipPercentageRetainedbyParentCompany" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="cst_StateofColoradoLitigationMember" name="StateofColoradoLitigationMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_StockBasedActivityAbstract" name="StockBasedActivityAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_StockOptionsandRestrictedStockUnitsRSUsMember" name="StockOptionsandRestrictedStockUnitsRSUsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_SwingLineLoansMember" name="SwingLineLoansMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="cst_TermofMaterialContract" name="TermofMaterialContract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_ThefiscalquarterendingDecember312014Member" name="ThefiscalquarterendingDecember312014Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_ThereafterDecember312014Member" name="ThereafterDecember312014Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_TwoQuartersFollowingClosingofMaterialAcquisitionMember" name="TwoQuartersFollowingClosingofMaterialAcquisitionMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_UponissuanceofQualifiedSeniorNotesMember" name="UponissuanceofQualifiedSeniorNotesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_UsefulLifeAxis" name="UsefulLifeAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_UsefulLifeDomain" name="UsefulLifeDomain" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="cst_ValeroEnergyCorporationMember" name="ValeroEnergyCorporationMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
</xsd:schema>


