<?xml version="1.0" encoding="US-ASCII"?>
<!--XBRL Document Created with WebFilings-->
<!-- -->
<xsd:schema attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://www.valero.com/20120930" 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:us-types="http://fasb.org/us-types/2012-01-31" xmlns:vlo="http://www.valero.com/20120930" 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/2012-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2012/elts/us-gaap-2012-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-roles/2012-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2012/elts/us-roles-2012-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-types/2012-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2012/elts/us-types-2012-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/2012-01-31" schemaLocation="http://xbrl.sec.gov/country/2012/country-2012-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/currency/2012-01-31" schemaLocation="http://xbrl.sec.gov/currency/2012/currency-2012-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/dei/2012-01-31" schemaLocation="http://xbrl.sec.gov/dei/2012/dei-2012-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/exch/2012-01-31" schemaLocation="http://xbrl.sec.gov/exch/2012/exch-2012-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/invest/2012-01-31" schemaLocation="http://xbrl.sec.gov/invest/2012/invest-2012-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="vlo-20120930_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="vlo-20120930_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="vlo-20120930_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="vlo-20120930_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:type="simple" />
      <link:roleType id="Acquisitions" roleURI="http://www.valero.com/role/Acquisitions">
        <link:definition>2103100 - 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="AcquisitionsDetails" roleURI="http://www.valero.com/role/AcquisitionsDetails">
        <link:definition>2403402 - Disclosure - Acquisitions (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.valero.com/role/AcquisitionsTables">
        <link:definition>2303301 - 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="BasisOfPresentationAndSummaryOfSignificantAccountingPolicies" roleURI="http://www.valero.com/role/BasisOfPresentationAndSummaryOfSignificantAccountingPolicies">
        <link:definition>2101100 - Disclosure - Basis of Presentation and Summary of 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="BasisOfPresentationAndSummaryOfSignificantAccountingPoliciesBasisOfPresentationAndSummaryOfSignificantAccountingPoliciesDetails" roleURI="http://www.valero.com/role/BasisOfPresentationAndSummaryOfSignificantAccountingPoliciesBasisOfPresentationAndSummaryOfSignificantAccountingPoliciesDetails">
        <link:definition>2401402 - Disclosure - Basis of Presentation and Summary of Significant Accounting Policies Basis of Presentation and Summary of Significant Accounting Policies (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="BasisOfPresentationAndSummaryOfSignificantAccountingPoliciesPolicies" roleURI="http://www.valero.com/role/BasisOfPresentationAndSummaryOfSignificantAccountingPoliciesPolicies">
        <link:definition>2201201 - Disclosure - Basis of Presentation and Summary of 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="CommitmentsAndContingencies" roleURI="http://www.valero.com/role/CommitmentsAndContingencies">
        <link:definition>2113100 - 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="CommitmentsAndContingenciesDetails" roleURI="http://www.valero.com/role/CommitmentsAndContingenciesDetails">
        <link:definition>2413401 - Disclosure - Commitments and Contingencies (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="ConsolidatedBalanceSheets" roleURI="http://www.valero.com/role/ConsolidatedBalanceSheets">
        <link:definition>1001000 - Statement - Consolidated Balance Sheets</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="ConsolidatedBalanceSheetsParenthetical" roleURI="http://www.valero.com/role/ConsolidatedBalanceSheetsParenthetical">
        <link:definition>1002500 - Statement - Consolidated Balance Sheets (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://www.valero.com/role/ConsolidatedStatementsOfCashFlowsUnaudited">
        <link:definition>1006000 - 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="ConsolidatedStatementsOfComprehensiveIncomeUnaudited" roleURI="http://www.valero.com/role/ConsolidatedStatementsOfComprehensiveIncomeUnaudited">
        <link:definition>1005000 - Statement - Consolidated Statements of Comprehensive Income (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="ConsolidatedStatementsOfIncomeUnaudited" roleURI="http://www.valero.com/role/ConsolidatedStatementsOfIncomeUnaudited">
        <link:definition>1004000 - Statement - Consolidated Statements of Income (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="ConsolidatedStatementsOfIncomeUnauditedCalc2" roleURI="http://www.valero.com/role/ConsolidatedStatementsOfIncomeUnauditedCalc2">
        <link:definition>1004000 - Statement - Consolidated Statements of Income (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="Debt" roleURI="http://www.valero.com/role/Debt">
        <link:definition>2112100 - 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="DebtBankDebtAndCreditFacilitiesDetails" roleURI="http://www.valero.com/role/DebtBankDebtAndCreditFacilitiesDetails">
        <link:definition>2412403 - Disclosure - Debt, Bank Debt and Credit Facilities (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="DebtDetails" roleURI="http://www.valero.com/role/DebtDetails">
        <link:definition>2412402 - Disclosure - 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="DebtTables" roleURI="http://www.valero.com/role/DebtTables">
        <link:definition>2312301 - 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="DocumentAndEntityInformation" roleURI="http://www.valero.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="EarningsPerCommonShare" roleURI="http://www.valero.com/role/EarningsPerCommonShare">
        <link:definition>2116100 - Disclosure - Earnings Per Common 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="EarningsPerCommonShareDetails" roleURI="http://www.valero.com/role/EarningsPerCommonShareDetails">
        <link:definition>2416402 - Disclosure - Earnings Per Common 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="EarningsPerCommonSharePotentiallyDilutiveSecuritiesDetails" roleURI="http://www.valero.com/role/EarningsPerCommonSharePotentiallyDilutiveSecuritiesDetails">
        <link:definition>2416403 - Disclosure - Earnings Per Common Share, Potentially Dilutive Securities (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="EarningsPerCommonShareTables" roleURI="http://www.valero.com/role/EarningsPerCommonShareTables">
        <link:definition>2316301 - Disclosure - Earnings Per Common 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.valero.com/role/EmployeeBenefitPlans">
        <link:definition>2115100 - 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="EmployeeBenefitPlansDetails" roleURI="http://www.valero.com/role/EmployeeBenefitPlansDetails">
        <link:definition>2415402 - Disclosure - Employee Benefit 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="EmployeeBenefitPlansTables" roleURI="http://www.valero.com/role/EmployeeBenefitPlansTables">
        <link:definition>2315301 - 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.valero.com/role/Equity">
        <link:definition>2114100 - 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="EquityDetails" roleURI="http://www.valero.com/role/EquityDetails">
        <link:definition>2414402 - Disclosure - Equity (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.valero.com/role/EquityTables">
        <link:definition>2314301 - 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.valero.com/role/FairValueMeasurements">
        <link:definition>2119100 - 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="FairValueMeasurementsLevel3ReconciliationDetails" roleURI="http://www.valero.com/role/FairValueMeasurementsLevel3ReconciliationDetails">
        <link:definition>2419404 - Disclosure - Fair Value Measurements, Level 3 Reconciliation (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="FairValueMeasurementsNonrecurringDetails" roleURI="http://www.valero.com/role/FairValueMeasurementsNonrecurringDetails">
        <link:definition>2419405 - Disclosure - Fair Value Measurements, Nonrecurring (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="FairValueMeasurementsOtherFinancialInstrumentsDetails" roleURI="http://www.valero.com/role/FairValueMeasurementsOtherFinancialInstrumentsDetails">
        <link:definition>2419406 - Disclosure - Fair Value Measurements. Other Financial Instruments (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="FairValueMeasurementsPolicies" roleURI="http://www.valero.com/role/FairValueMeasurementsPolicies">
        <link:definition>2219201 - Disclosure - Fair Value Measurements (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="FairValueMeasurementsRecurringDetails" roleURI="http://www.valero.com/role/FairValueMeasurementsRecurringDetails">
        <link:definition>2419403 - Disclosure - Fair Value Measurements, Recurring (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.valero.com/role/FairValueMeasurementsTables">
        <link:definition>2319302 - 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="Impairments" roleURI="http://www.valero.com/role/Impairments">
        <link:definition>2106100 - Disclosure - 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="ImpairmentsDetails" roleURI="http://www.valero.com/role/ImpairmentsDetails">
        <link:definition>2406401 - Disclosure - 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="Inventories" roleURI="http://www.valero.com/role/Inventories">
        <link:definition>2107100 - 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.valero.com/role/InventoriesDetails">
        <link:definition>2407402 - 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="InventoriesTables" roleURI="http://www.valero.com/role/InventoriesTables">
        <link:definition>2307301 - 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="PriceRiskManagementActivities" roleURI="http://www.valero.com/role/PriceRiskManagementActivities">
        <link:definition>2120100 - Disclosure - Price Risk Management Activities</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="PriceRiskManagementActivitiesDetails" roleURI="http://www.valero.com/role/PriceRiskManagementActivitiesDetails">
        <link:definition>2420403 - Disclosure - Price Risk Management Activities (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="PriceRiskManagementActivitiesGainLossByIncomeStatementLocationDetails" roleURI="http://www.valero.com/role/PriceRiskManagementActivitiesGainLossByIncomeStatementLocationDetails">
        <link:definition>2420405 - Disclosure - Price Risk Management Activities, Gain (Loss) by Income Statement Location (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="PriceRiskManagementActivitiesHedgingInstrumentsByConsolidatedBalanceSheetLocationDetails" roleURI="http://www.valero.com/role/PriceRiskManagementActivitiesHedgingInstrumentsByConsolidatedBalanceSheetLocationDetails">
        <link:definition>2420404 - Disclosure - Price Risk Management Activities, Hedging Instruments by Consolidated Balance Sheet Location (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="PriceRiskManagementActivitiesPolicies" roleURI="http://www.valero.com/role/PriceRiskManagementActivitiesPolicies">
        <link:definition>2220201 - Disclosure - Price Risk Management Activities (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="PriceRiskManagementActivitiesTables" roleURI="http://www.valero.com/role/PriceRiskManagementActivitiesTables">
        <link:definition>2320302 - Disclosure - Price Risk Management Activities (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.valero.com/role/SegmentInformation">
        <link:definition>2117100 - 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="SegmentInformationDetails" roleURI="http://www.valero.com/role/SegmentInformationDetails">
        <link:definition>2417402 - Disclosure - Segment 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="SegmentInformationTables" roleURI="http://www.valero.com/role/SegmentInformationTables">
        <link:definition>2317301 - 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="SupplementalCashFlowInformation" roleURI="http://www.valero.com/role/SupplementalCashFlowInformation">
        <link:definition>2118100 - 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="SupplementalCashFlowInformationDetails" roleURI="http://www.valero.com/role/SupplementalCashFlowInformationDetails">
        <link:definition>2418402 - Disclosure - Supplemental Cash Flow 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="SupplementalCashFlowInformationTables" roleURI="http://www.valero.com/role/SupplementalCashFlowInformationTables">
        <link:definition>2318301 - 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="vlo_AccountsReceivableSalesFacilityAbstract" name="AccountsReceivableSalesFacilityAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_AccountsReceivableSalesFacilityMaximumBorrowingCapacity" name="AccountsReceivableSalesFacilityMaximumBorrowingCapacity" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="vlo_AccountsReceivableSalesFacilityTextualAbstract" name="AccountsReceivableSalesFacilityTextualAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_AccrualForTaxesOtherThanIncomeTaxesIncludingAdValoremExciseSalesAndUseAndPayroll" name="AccrualForTaxesOtherThanIncomeTaxesIncludingAdValoremExciseSalesAndUseAndPayroll" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="vlo_AccruedExpensesMember" name="AccruedExpensesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_AcquisitionsTextualsAbstract" name="AcquisitionsTextualsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_ArubaRefineryMember" name="ArubaRefineryMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_BankCreditAgreementsAbstract" name="BankCreditAgreementsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_BasisOfPresentationAndSummaryOfSignificantAccountingPoliciesAbstract" name="BasisOfPresentationAndSummaryOfSignificantAccountingPoliciesAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_BiofuelsBlendingMember" name="BiofuelsBlendingMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_BusinessAcquisitionCostOfAcquiredEntityPurchasePriceOfWorkingCapital" name="BusinessAcquisitionCostOfAcquiredEntityPurchasePriceOfWorkingCapital" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="vlo_BusinessAcquisitionPurchasePriceAllocationAssetsAcquiredLiabilitiesAssumedNetOfCashAcquired" name="BusinessAcquisitionPurchasePriceAllocationAssetsAcquiredLiabilitiesAssumedNetOfCashAcquired" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="vlo_BusinessAcquisitionPurchasePriceAllocationCurrentLiabilitiesCurrentLiabilitiesLessCurrentPortionOfDebtAndCapitalLeaseObligations" name="BusinessAcquisitionPurchasePriceAllocationCurrentLiabilitiesCurrentLiabilitiesLessCurrentPortionOfDebtAndCapitalLeaseObligations" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="vlo_BusinessAcquisitionPurchasePriceAllocationDebtAndCapitalLeasesAssumed" name="BusinessAcquisitionPurchasePriceAllocationDebtAndCapitalLeasesAssumed" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="vlo_BusinessCombinationProvisionalInformationInitialAccountingIncompleteAdjustmentDeferredTaxLiabilities" name="BusinessCombinationProvisionalInformationInitialAccountingIncompleteAdjustmentDeferredTaxLiabilities" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="vlo_BusinessCombinationProvisionalInformationInitialAccountingIncompleteAdjustmentOtherNoncurrentLiabilities" name="BusinessCombinationProvisionalInformationInitialAccountingIncompleteAdjustmentOtherNoncurrentLiabilities" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_CanadianRevolverLetterOfCreditMember" name="CanadianRevolverLetterOfCreditMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_CanadianRevolverMember" name="CanadianRevolverMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_CashFlowsRelatedToInterestAndIncomeTaxesAbstract" name="CashFlowsRelatedToInterestAndIncomeTaxesAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_CashFlowsRelatedToInterestAndIncomeTaxesTextBlock" name="CashFlowsRelatedToInterestAndIncomeTaxesTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_CertainBenefitPlansMember" name="CertainBenefitPlansMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_CommitmentsAndContingenciesTextualsAbstract" name="CommitmentsAndContingenciesTextualsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_CommittedMember" name="CommittedMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_ComplianceProgramsAxis" name="ComplianceProgramsAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_ComplianceProgramsTypeDomain" name="ComplianceProgramsTypeDomain" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_CreditFacilityAbstract" name="CreditFacilityAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_DebtInstrumentMandatoryTenderDate" name="DebtInstrumentMandatoryTenderDate" nillable="true" substitutionGroup="xbrli:item" type="xbrli:dateItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_DebtToCapitalizationRatiosAsPerTermsOfRevolver" name="DebtToCapitalizationRatiosAsPerTermsOfRevolver" nillable="true" substitutionGroup="xbrli:item" type="xbrli:pureItemType" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="vlo_DerivativeByTransactionAxis" name="DerivativeByTransactionAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_DerivativeByTransactionPurchasesAndSalesDomain" name="DerivativeByTransactionPurchasesAndSalesDomain" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_DocumentAndEntityInformationAbstract" name="DocumentAndEntityInformationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_EarningsLossPerCommonShareFromContinuingOperationsAbstract" name="EarningsLossPerCommonShareFromContinuingOperationsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_EffectOfDerivativeInstrumentsOnStatementsOfIncomeAbstract" name="EffectOfDerivativeInstrumentsOnStatementsOfIncomeAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_EligibleReceivablesSoldToThirdPartyEntitiesAndFinancialInstitutions" name="EligibleReceivablesSoldToThirdPartyEntitiesAndFinancialInstitutions" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="vlo_EmissionAllowancesMember" name="EmissionAllowancesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_EmissionsAllowanceMember" name="EmissionsAllowanceMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_EmployeeBenefitPlansTextualsAbstract" name="EmployeeBenefitPlansTextualsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_EthanolFeedstocksAndProducts" name="EthanolFeedstocksAndProducts" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="vlo_EthanolMember" name="EthanolMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_EthanolOperatingCostsAndExpenses" name="EthanolOperatingCostsAndExpenses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="vlo_ExtendedTermOfAccountsReceivableSalesFacility" name="ExtendedTermOfAccountsReceivableSalesFacility" nillable="true" substitutionGroup="xbrli:item" type="us-types:dateStringItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_FairValueConcentrationOfRiskCollateralPolicyPolicyTextBlock" name="FairValueConcentrationOfRiskCollateralPolicyPolicyTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_FairValueMeasurementsOtherFinancialInstrumentsAbstract" name="FairValueMeasurementsOtherFinancialInstrumentsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_FairValueMeasurementsPoliciesAbstract" name="FairValueMeasurementsPoliciesAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_FairValueMeasurementsTextualsAbstract" name="FairValueMeasurementsTextualsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_FinancialServicesIndustryMember" name="FinancialServicesIndustryMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_ForeignCurrencyContractMember" name="ForeignCurrencyContractMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_GrainInBushelsMember" name="GrainInBushelsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_GulfOpportunityZoneRevenueBondsSeries2010Member" name="GulfOpportunityZoneRevenueBondsSeries2010Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_IndustrialRevenueBondsTaxExemptRefundingBondsMember" name="IndustrialRevenueBondsTaxExemptRefundingBondsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_InventoriesTextualsAbstract" name="InventoriesTextualsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_InventoryMember" name="InventoryMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_InventoryRelatedAssetsMember" name="InventoryRelatedAssetsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_LineOfCreditFacilityExpirationDateMonthYear" name="LineOfCreditFacilityExpirationDateMonthYear" nillable="true" substitutionGroup="xbrli:item" type="us-types:dateStringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_MaturityCurrentYearMember" name="MaturityCurrentYearMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_MaturityTimePeriodAxis" name="MaturityTimePeriodAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_MaturityTimePeriodDomain" name="MaturityTimePeriodDomain" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_MaturityYearThreeMember" name="MaturityYearThreeMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_MaturityYearTwoMember" name="MaturityYearTwoMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_MerauxAcquisitionMember" name="MerauxAcquisitionMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_MinimumInventoryMember" name="MinimumInventoryMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_NaturalGasInBtusMember" name="NaturalGasInBtusMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_NonBankDebtAbstract" name="NonBankDebtAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_NonBindingPurchaseOffer" name="NonBindingPurchaseOffer" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="vlo_NotesDueIn2012Member" name="NotesDueIn2012Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_OtherDebtMember" name="OtherDebtMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_OtherIncomeExpenseMember" name="OtherIncomeExpenseMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_OtherLetterOfCreditMember" name="OtherLetterOfCreditMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_PembrokeAcquisitionMember" name="PembrokeAcquisitionMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_PrepaidExpensesAndOtherCurrentAssetsMember" name="PrepaidExpensesAndOtherCurrentAssetsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_PriceRiskManagementActivitiesPoliciesAbstract" name="PriceRiskManagementActivitiesPoliciesAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_PriceRiskManagementActivitiesTextualAbstract" name="PriceRiskManagementActivitiesTextualAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_PurchasesLongMember" name="PurchasesLongMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_RedemptionValuePercentageOfStatedValue" name="RedemptionValuePercentageOfStatedValue" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_RefiningAssetsMember" name="RefiningAssetsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_RefiningIndustryMember" name="RefiningIndustryMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_RefiningMember" name="RefiningMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_RefiningOperatingCostsAndExpenses" name="RefiningOperatingCostsAndExpenses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_ReportableSegmentTotalAssetsAbstract" name="ReportableSegmentTotalAssetsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_RetailMember" name="RetailMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_SalesShortMember" name="SalesShortMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_ScheduleOfChangesInAccountsReceivableSalesFacilityTableTextBlock" name="ScheduleOfChangesInAccountsReceivableSalesFacilityTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_SeniorNotesDueInFebruary2011Member" name="SeniorNotesDueInFebruary2011Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_SeniorNotesDueInMay2011Member" name="SeniorNotesDueInMay2011Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_StockIssuedOrRepurchasedDuringPeriodValueShareBasedCompensationAbstract" name="StockIssuedOrRepurchasedDuringPeriodValueShareBasedCompensationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_SupplementalInformationAbstract" name="SupplementalInformationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_TaxExemptRevenueRefundingBondsSeries1997AMember" name="TaxExemptRevenueRefundingBondsSeries1997AMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_TaxExemptRevenueRefundingBondsSeries1997BMember" name="TaxExemptRevenueRefundingBondsSeries1997BMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_TaxExemptRevenueRefundingBondsSeries1997CMember" name="TaxExemptRevenueRefundingBondsSeries1997CMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_TaxExemptWasteDisposalRevenueBondsSeries1997Member" name="TaxExemptWasteDisposalRevenueBondsSeries1997Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_TaxExemptWasteDisposalRevenueBondsSeries1998Member" name="TaxExemptWasteDisposalRevenueBondsSeries1998Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_TaxExemptWasteDisposalRevenueBondsSeries1999Member" name="TaxExemptWasteDisposalRevenueBondsSeries1999Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_TaxExemptWasteDisposalRevenueBondsSeries2001Member" name="TaxExemptWasteDisposalRevenueBondsSeries2001Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_TerminalAssetsMember" name="TerminalAssetsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_USRevolverLetterOfCreditMember" name="USRevolverLetterOfCreditMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_USRevolverMember" name="USRevolverMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_UncommittedMember" name="UncommittedMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_VolumeOfOutstandingContractCashFlowHedgesTableTextBlock" name="VolumeOfOutstandingContractCashFlowHedgesTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="vlo_VolumeOfOutstandingContractsAbstract" name="VolumeOfOutstandingContractsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_VolumeOfOutstandingContractsEconomicHedgesTextBlock" name="VolumeOfOutstandingContractsEconomicHedgesTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_VolumeOfOutstandingContractsFairValueHedgesTextBlock" name="VolumeOfOutstandingContractsFairValueHedgesTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="vlo_VolumeOfOutstandingContractsTradingActivitiesTextBlock" name="VolumeOfOutstandingContractsTradingActivitiesTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
</xsd:schema>
