<?xml version="1.0" encoding="us-ascii"?>
<!--XBRL document created by Certent Disclosure Management 6.2.0.61 -->
<!--Based on XBRL 2.1-->
<!--Created on: 9/7/2016 3:55:14 PM-->
<!--Modified on: 9/7/2016 3:55:14 PM-->
<schema targetNamespace="http://www.footlocker-inc.com/20160730" elementFormDefault="qualified" xmlns="http://www.w3.org/2001/XMLSchema" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:xbrldt="http://xbrl.org/2005/xbrldt" xmlns:xl="http://www.xbrl.org/2003/XLink" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:country="http://xbrl.sec.gov/country/2013-01-31" xmlns:currency="http://xbrl.sec.gov/currency/2014-01-31" xmlns:dei="http://xbrl.sec.gov/dei/2014-01-31" xmlns:invest="http://xbrl.sec.gov/invest/2013-01-31" xmlns:naics="http://xbrl.sec.gov/naics/2011-01-31" xmlns:sic="http://xbrl.sec.gov/sic/2011-01-31" xmlns:stpr="http://xbrl.sec.gov/stpr/2011-01-31" xmlns:deprecated="http://www.xbrl.org/2009/arcrole/fact-explanatoryFact" xmlns:nonnum="http://www.xbrl.org/dtr/type/non-numeric" xmlns:num="http://www.xbrl.org/dtr/type/numeric" xmlns:fl="http://www.footlocker-inc.com/20160730" xmlns:us-gaap="http://fasb.org/us-gaap/2016-01-31" xmlns:us-types="http://fasb.org/us-types/2016-01-31" xmlns:exch="http://xbrl.sec.gov/exch/2016-01-31">
  <annotation>
    <appinfo>
      <link:roleType roleURI="http://www.footlocker-inc.com/role/StatementCondensedConsolidatedBalanceSheets" id="StatementCondensedConsolidatedBalanceSheets">
        <link:definition>00100 - Statement - CONDENSED 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 roleURI="http://www.footlocker-inc.com/role/StatementCondensedConsolidatedStatementsOfOperations" id="StatementCondensedConsolidatedStatementsOfOperations">
        <link:definition>00200 - Statement - CONDENSED CONSOLIDATED STATEMENTS OF OPERATIONS</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.footlocker-inc.com/role/StatementCondensedConsolidatedStatementsOfComprehensiveIncome" id="StatementCondensedConsolidatedStatementsOfComprehensiveIncome">
        <link:definition>00300 - Statement - CONDENSED CONSOLIDATED STATEMENTS OF COMPREHENSIVE 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 roleURI="http://www.footlocker-inc.com/role/StatementCondensedConsolidatedStatementsOfCashFlows" id="StatementCondensedConsolidatedStatementsOfCashFlows">
        <link:definition>00400 - Statement - CONDENSED CONSOLIDATED STATEMENTS 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 roleURI="http://www.footlocker-inc.com/role/DisclosureSegmentInformationSalesAndDivisionOperatingResultsForReportableSegmentsDetails" id="DisclosureSegmentInformationSalesAndDivisionOperatingResultsForReportableSegmentsDetails">
        <link:definition>40202 - Disclosure - Segment Information (Sales and Division Operating Results for Reportable Segments) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureOtherIntangibleAssetsNetScheduleOfOtherIntangibleAssetsDetails" id="DisclosureOtherIntangibleAssetsNetScheduleOfOtherIntangibleAssetsDetails">
        <link:definition>40402 - Disclosure - Other Intangible Assets, Net (Schedule of Other 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 roleURI="http://www.footlocker-inc.com/role/DisclosureAccumulatedOtherComprehensiveLossScheduleOfAccumulatedOtherComprehensiveLossDetails" id="DisclosureAccumulatedOtherComprehensiveLossScheduleOfAccumulatedOtherComprehensiveLossDetails">
        <link:definition>40501 - Disclosure - Accumulated Other Comprehensive Loss (Schedule of Accumulated Other Comprehensive Loss) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureAccumulatedOtherComprehensiveLossReclassificationsFromAccumulatedOtherComprehensiveLossDetails" id="DisclosureAccumulatedOtherComprehensiveLossReclassificationsFromAccumulatedOtherComprehensiveLossDetails">
        <link:definition>40503 - Disclosure - Accumulated Other Comprehensive Loss (Reclassifications from Accumulated Other Comprehensive Loss) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureEarningsPerShareComputationOfBasicAndDilutedEarningsPerShareDetails" id="DisclosureEarningsPerShareComputationOfBasicAndDilutedEarningsPerShareDetails">
        <link:definition>40902 - Disclosure - Earnings Per Share (Computation of Basic and Diluted 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 roleURI="http://www.footlocker-inc.com/role/DisclosurePensionAndPostretirementPlansNetBenefitExpenseIncomeDetails" id="DisclosurePensionAndPostretirementPlansNetBenefitExpenseIncomeDetails">
        <link:definition>41005 - Disclosure - Pension and Postretirement Plans (Net Benefit Expense (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 roleURI="http://www.footlocker-inc.com/role/DocumentDocumentAndEntityInformation" id="DocumentDocumentAndEntityInformation">
        <link:definition>00090 - 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 roleURI="http://www.footlocker-inc.com/role/StatementCondensedConsolidatedBalanceSheetsParenthetical" id="StatementCondensedConsolidatedBalanceSheetsParenthetical">
        <link:definition>00101 - Statement - CONDENSED 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 roleURI="http://www.footlocker-inc.com/role/StatementCondensedConsolidatedStatementsOfComprehensiveIncomeParenthetical" id="StatementCondensedConsolidatedStatementsOfComprehensiveIncomeParenthetical">
        <link:definition>00301 - Statement - CONDENSED CONSOLIDATED STATEMENTS OF COMPREHENSIVE INCOME (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 roleURI="http://www.footlocker-inc.com/role/DisclosureSummaryOfSignificantAccountingPolicies" id="DisclosureSummaryOfSignificantAccountingPolicies">
        <link:definition>10101 - Disclosure - 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 roleURI="http://www.footlocker-inc.com/role/DisclosureSegmentInformation" id="DisclosureSegmentInformation">
        <link:definition>10201 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosureGoodwill" id="DisclosureGoodwill">
        <link:definition>10301 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosureOtherIntangibleAssetsNet" id="DisclosureOtherIntangibleAssetsNet">
        <link:definition>10401 - Disclosure - Other Intangible Assets, net</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.footlocker-inc.com/role/DisclosureAccumulatedOtherComprehensiveLoss" id="DisclosureAccumulatedOtherComprehensiveLoss">
        <link:definition>10501 - Disclosure - Accumulated Other Comprehensive Loss</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.footlocker-inc.com/role/DisclosureRevolvingCreditFacility" id="DisclosureRevolvingCreditFacility">
        <link:definition>10601 - Disclosure - Revolving Credit Facility</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.footlocker-inc.com/role/DisclosureFinancialInstruments" id="DisclosureFinancialInstruments">
        <link:definition>10701 - Disclosure - Financial Instruments</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.footlocker-inc.com/role/DisclosureFairValueMeasurements" id="DisclosureFairValueMeasurements">
        <link:definition>10801 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosureEarningsPerShare" id="DisclosureEarningsPerShare">
        <link:definition>10901 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosurePensionAndPostretirementPlans" id="DisclosurePensionAndPostretirementPlans">
        <link:definition>11001 - Disclosure - Pension and Postretirement 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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensation" id="DisclosureShareBasedCompensation">
        <link:definition>11101 - Disclosure - Share-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 roleURI="http://www.footlocker-inc.com/role/DisclosureLegalProceedings" id="DisclosureLegalProceedings">
        <link:definition>11201 - Disclosure - Legal Proceedings</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.footlocker-inc.com/role/DisclosureSummaryOfSignificantAccountingPoliciesPolicy" id="DisclosureSummaryOfSignificantAccountingPoliciesPolicy">
        <link:definition>20102 - Disclosure - Summary of Significant Accounting Policies (Policy)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.footlocker-inc.com/role/DisclosureSegmentInformationTables" id="DisclosureSegmentInformationTables">
        <link:definition>30203 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosureGoodwillTables" id="DisclosureGoodwillTables">
        <link:definition>30303 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosureOtherIntangibleAssetsNetTables" id="DisclosureOtherIntangibleAssetsNetTables">
        <link:definition>30403 - Disclosure - Other Intangible Assets, net (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 roleURI="http://www.footlocker-inc.com/role/DisclosureAccumulatedOtherComprehensiveLossTables" id="DisclosureAccumulatedOtherComprehensiveLossTables">
        <link:definition>30503 - Disclosure - Accumulated Other Comprehensive Loss (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 roleURI="http://www.footlocker-inc.com/role/DisclosureFinancialInstrumentsTables" id="DisclosureFinancialInstrumentsTables">
        <link:definition>30703 - Disclosure - Financial Instruments (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 roleURI="http://www.footlocker-inc.com/role/DisclosureFairValueMeasurementsTables" id="DisclosureFairValueMeasurementsTables">
        <link:definition>30803 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosureEarningsPerShareTables" id="DisclosureEarningsPerShareTables">
        <link:definition>30903 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosureRetirementPlansAndOtherBenefitsTables" id="DisclosureRetirementPlansAndOtherBenefitsTables">
        <link:definition>31003 - Disclosure - Retirement Plans and Other Benefits (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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensationTables" id="DisclosureShareBasedCompensationTables">
        <link:definition>31103 - Disclosure - Share-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 roleURI="http://www.footlocker-inc.com/role/DisclosureSegmentInformationNarrativeDetails" id="DisclosureSegmentInformationNarrativeDetails">
        <link:definition>40201 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosureGoodwillScheduleOfGoodwillDetails" id="DisclosureGoodwillScheduleOfGoodwillDetails">
        <link:definition>40302 - Disclosure - Goodwill (Schedule of 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 roleURI="http://www.footlocker-inc.com/role/DisclosureOtherIntangibleAssetsNetNarrativeDetails" id="DisclosureOtherIntangibleAssetsNetNarrativeDetails">
        <link:definition>40401 - Disclosure - Other Intangible Assets, Net (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 roleURI="http://www.footlocker-inc.com/role/DisclosureOtherIntangibleAssetsNetAmortizationExpenseDetails" id="DisclosureOtherIntangibleAssetsNetAmortizationExpenseDetails">
        <link:definition>40403 - Disclosure - Other Intangible Assets, Net (Amortization 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 roleURI="http://www.footlocker-inc.com/role/DisclosureOtherIntangibleAssetsNetEstimatedFutureAmortizationExpenseForFiniteLivedIntangiblesDetails" id="DisclosureOtherIntangibleAssetsNetEstimatedFutureAmortizationExpenseForFiniteLivedIntangiblesDetails">
        <link:definition>40404 - Disclosure - Other Intangible Assets, Net (Estimated Future Amortization Expense for Finite Lived Intangibles) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureAccumulatedOtherComprehensiveLossChangesInAccumulatedOtherComprehensiveLossDetails" id="DisclosureAccumulatedOtherComprehensiveLossChangesInAccumulatedOtherComprehensiveLossDetails">
        <link:definition>40502 - Disclosure - Accumulated Other Comprehensive Loss (Changes in Accumulated Other Comprehensive Loss) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureRevolvingCreditFacilityNarrativeDetails" id="DisclosureRevolvingCreditFacilityNarrativeDetails">
        <link:definition>40601 - Disclosure - Revolving 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 roleURI="http://www.footlocker-inc.com/role/DisclosureFinancialInstrumentsNarrativeDetails" id="DisclosureFinancialInstrumentsNarrativeDetails">
        <link:definition>40701 - Disclosure - Financial Instruments (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 roleURI="http://www.footlocker-inc.com/role/DisclosureFinancialInstrumentsFairValueDerivativeContractsOnGrossBasisByTypeOfContractDetails" id="DisclosureFinancialInstrumentsFairValueDerivativeContractsOnGrossBasisByTypeOfContractDetails">
        <link:definition>40702 - Disclosure - Financial Instruments (Fair Value Derivative Contracts on Gross Basis by Type of Contract) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureFairValueMeasurementsAssetsAndLiabilitiesMeasuredAtFairValueOnRecurringBasisDetails" id="DisclosureFairValueMeasurementsAssetsAndLiabilitiesMeasuredAtFairValueOnRecurringBasisDetails">
        <link:definition>40801 - Disclosure - Fair Value Measurements (Assets and Liabilities Measured at Fair Value on Recurring Basis) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureFairValueMeasurementsCarryingValueAndEstimatedFairValueOfLongTermDebtDetails" id="DisclosureFairValueMeasurementsCarryingValueAndEstimatedFairValueOfLongTermDebtDetails">
        <link:definition>40802 - Disclosure - Fair Value Measurements (Carrying Value and Estimated Fair Value 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 roleURI="http://www.footlocker-inc.com/role/DisclosureEarningsPerShareNarrativeDetails" id="DisclosureEarningsPerShareNarrativeDetails">
        <link:definition>40901 - 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 roleURI="http://www.footlocker-inc.com/role/DisclosurePensionAndPostretirementPlansNarrativeDetails" id="DisclosurePensionAndPostretirementPlansNarrativeDetails">
        <link:definition>41001 - Disclosure - Pension and Postretirement 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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensationNarrativeDetails" id="DisclosureShareBasedCompensationNarrativeDetails">
        <link:definition>41101 - Disclosure - Share-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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensationTotalCompensationExpenseIncludedInSgAndRelatedTaxBenefitsRecognizedDetails" id="DisclosureShareBasedCompensationTotalCompensationExpenseIncludedInSgAndRelatedTaxBenefitsRecognizedDetails">
        <link:definition>41102 - Disclosure - Share-Based Compensation (Total compensation expense included in SG&amp;A and the related tax benefits recognized) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensationAssumptionsUsedToComputeShareBasedCompensationExpenseDetails" id="DisclosureShareBasedCompensationAssumptionsUsedToComputeShareBasedCompensationExpenseDetails">
        <link:definition>41103 - Disclosure - Share-Based Compensation (Assumptions Used to Compute Share-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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensationOptionsGrantedUnderStockOptionPlansDetails" id="DisclosureShareBasedCompensationOptionsGrantedUnderStockOptionPlansDetails">
        <link:definition>41104 - Disclosure - Share-Based Compensation (Options Granted Under Stock Option 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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensationTotalIntrinsicValueOfOptionsExercisedDetails" id="DisclosureShareBasedCompensationTotalIntrinsicValueOfOptionsExercisedDetails">
        <link:definition>41105 - Disclosure - Share-Based Compensation (Total Intrinsic Value of Options Exercised) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensationAggregateIntrinsicValueForStockOptionsOutstandingAndExercisableDetails" id="DisclosureShareBasedCompensationAggregateIntrinsicValueForStockOptionsOutstandingAndExercisableDetails">
        <link:definition>41106 - Disclosure - Share-Based Compensation (Aggregate Intrinsic Value for Stock Options Outstanding and Exercisable) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensationInformationAboutStockOptionsOutstandingAndExercisableDetails" id="DisclosureShareBasedCompensationInformationAboutStockOptionsOutstandingAndExercisableDetails">
        <link:definition>41108 - Disclosure - Share-Based Compensation (Information about Stock Options Outstanding and Exercisable) (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 roleURI="http://www.footlocker-inc.com/role/DisclosureShareBasedCompensationChangesInNonvestedOptionsDetails" id="DisclosureShareBasedCompensationChangesInNonvestedOptionsDetails">
        <link:definition>41109 - Disclosure - Share-Based Compensation (Changes in Nonvested 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 roleURI="http://www.footlocker-inc.com/role/DisclosureLegalProceedingsNarrativeDetails" id="DisclosureLegalProceedingsNarrativeDetails">
        <link:definition>41201 - Disclosure - Legal Proceedings (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:linkbaseRef xlink:type="simple" xlink:href="fl-20160730_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" />
      <link:linkbaseRef xlink:type="simple" xlink:href="fl-20160730_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" />
      <link:linkbaseRef xlink:type="simple" xlink:href="fl-20160730_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" />
      <link:linkbaseRef xlink:type="simple" xlink:href="fl-20160730_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" />
    </appinfo>
  </annotation>
  <import namespace="http://www.xbrl.org/2003/instance" schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd" />
  <import namespace="http://www.xbrl.org/2003/linkbase" schemaLocation="http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd" />
  <import namespace="http://xbrl.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd" />
  <import namespace="http://fasb.org/us-gaap/2016-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2016/elts/us-gaap-2016-01-31.xsd" />
  <import namespace="http://xbrl.sec.gov/invest/2013-01-31" schemaLocation="http://xbrl.sec.gov/invest/2013/invest-2013-01-31.xsd" />
  <import namespace="http://www.xbrl.org/2009/role/negated" schemaLocation="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd" />
  <import namespace="http://www.xbrl.org/2009/role/net" schemaLocation="http://www.xbrl.org/lrr/role/net-2009-12-16.xsd" />
  <import namespace="http://xbrl.sec.gov/dei/2014-01-31" schemaLocation="http://xbrl.sec.gov/dei/2014/dei-2014-01-31.xsd" />
  <import namespace="http://www.xbrl.org/dtr/type/numeric" schemaLocation="http://www.xbrl.org/dtr/type/numeric-2009-12-16.xsd" />
  <import namespace="http://www.xbrl.org/dtr/type/non-numeric" schemaLocation="http://www.xbrl.org/dtr/type/nonNumeric-2009-12-16.xsd" />
  <element name="FairValueAssetsAndLiabilitiesMeasuredOnRecurringBasisUnobservableInputReconciliationTable" type="xbrli:stringItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrldt:hypercubeItem" id="fl_FairValueAssetsAndLiabilitiesMeasuredOnRecurringBasisUnobservableInputReconciliationTable" />
  <element name="FairValueAssetsAndLiabilitiesMeasuredOnRecurringBasisUnobservableInputReconciliationLineItems" type="xbrli:stringItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_FairValueAssetsAndLiabilitiesMeasuredOnRecurringBasisUnobservableInputReconciliationLineItems" />
  <element name="ScheduleOfShareBasedCompensationArrangementByShareBasedPaymentAwardAwardTypeAndPlanNamesAxis" type="xbrli:stringItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrldt:dimensionItem" id="fl_ScheduleOfShareBasedCompensationArrangementByShareBasedPaymentAwardAwardTypeAndPlanNamesAxis" />
  <element name="ScheduleOfShareBasedCompensationArrangementByShareBasedPaymentAwardAwardTypeAndPlansNameDomain" type="nonnum:domainItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_ScheduleOfShareBasedCompensationArrangementByShareBasedPaymentAwardAwardTypeAndPlansNameDomain" />
  <element name="UnvestedOptionsMember" type="nonnum:domainItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_UnvestedOptionsMember" />
  <element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsAggregateIntrinsicValueAbstract" type="xbrli:stringItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsAggregateIntrinsicValueAbstract" />
  <element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsOutstandingAndExercisableAggregateIntrinsicValue" type="xbrli:monetaryItemType" abstract="false" xbrli:periodType="instant" nillable="true" xbrli:balance="debit" substitutionGroup="xbrli:item" id="fl_ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsOutstandingAndExercisableAggregateIntrinsicValue" />
  <element name="RangeOneMember" type="nonnum:domainItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_RangeOneMember" />
  <element name="RangeTwoMember" type="nonnum:domainItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_RangeTwoMember" />
  <element name="RangeThreeMember" type="nonnum:domainItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_RangeThreeMember" />
  <element name="RangeFourMember" type="nonnum:domainItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_RangeFourMember" />
  <element name="LineOfCreditFacilitiesTextBlock" type="nonnum:textBlockItemType" abstract="false" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_LineOfCreditFacilitiesTextBlock" />
  <element name="ScheduleOfIntangibleAssetsByMajorClassTableTextBlock" type="nonnum:textBlockItemType" abstract="false" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_ScheduleOfIntangibleAssetsByMajorClassTableTextBlock" />
  <element name="ScheduleOfChangesInAccumulatedOtherComprehensiveIncomeTableTextBlock" type="nonnum:textBlockItemType" abstract="false" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_ScheduleOfChangesInAccumulatedOtherComprehensiveIncomeTableTextBlock" />
  <element id="fl_IntrinsicValueOfOptionsOutstandingAndExercisableTablTextBlock" name="IntrinsicValueOfOptionsOutstandingAndExercisableTablTextBlock" nillable="true" type="nonnum:textBlockItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" />
  <element id="fl_ContingentlyIssuableSharesExcludedFromDilutedEarningsPerShare" name="ContingentlyIssuableSharesExcludedFromDilutedEarningsPerShare" nillable="true" type="xbrli:sharesItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" />
  <element name="OperatingIncomeLossBeforeRestructuringChargesCredits" type="xbrli:monetaryItemType" abstract="false" xbrli:periodType="duration" nillable="true" xbrli:balance="credit" substitutionGroup="xbrli:item" id="fl_OperatingIncomeLossBeforeRestructuringChargesCredits" />
  <element name="OperatingIncomeLossBeforeCorporateCostsAndOther" type="xbrli:monetaryItemType" abstract="false" xbrli:periodType="duration" nillable="true" xbrli:balance="credit" substitutionGroup="xbrli:item" id="fl_OperatingIncomeLossBeforeCorporateCostsAndOther" />
  <element name="CorporateCostsAndOther" type="xbrli:monetaryItemType" abstract="false" xbrli:periodType="duration" nillable="true" xbrli:balance="debit" substitutionGroup="xbrli:item" id="fl_CorporateCostsAndOther" />
  <element name="RunnersPointGroupMember" type="nonnum:domainItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_RunnersPointGroupMember" />
  <element name="ScheduleOfIntangibleAssetsByMajorClassTable" type="xbrli:stringItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrldt:hypercubeItem" id="fl_ScheduleOfIntangibleAssetsByMajorClassTable" />
  <element name="FavorableLeasesAndOtherMember" type="nonnum:domainItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_FavorableLeasesAndOtherMember" />
  <element name="IntangibleAssetsByMajorClassLineItems" type="xbrli:stringItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_IntangibleAssetsByMajorClassLineItems" />
  <element name="DebtDisclosureTable" type="xbrli:stringItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrldt:hypercubeItem" id="fl_DebtDisclosureTable" />
  <element id="fl_LineOfCreditFacilityAdditionalBorrowingCapacity" name="LineOfCreditFacilityAdditionalBorrowingCapacity" nillable="true" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" xbrli:balance="credit" />
  <element name="CovenantPercentage" type="num:percentItemType" abstract="false" xbrli:periodType="instant" nillable="true" substitutionGroup="xbrli:item" id="fl_CovenantPercentage" />
  <element name="CreditFacilityInterestExpense" type="xbrli:monetaryItemType" abstract="false" xbrli:periodType="duration" nillable="true" xbrli:balance="debit" substitutionGroup="xbrli:item" id="fl_CreditFacilityInterestExpense" />
  <element name="ReclassificationAdjustmentOutOfAccumulatedOtherComprehensiveIncomeTable" type="xbrli:stringItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrldt:hypercubeItem" id="fl_ReclassificationAdjustmentOutOfAccumulatedOtherComprehensiveIncomeTable" />
  <element name="DerivativeMaturityMonthAndYear" type="xbrli:gYearMonthItemType" abstract="false" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_DerivativeMaturityMonthAndYear" />
  <element name="DocumentAndEntityInformationAbstract" type="xbrli:stringItemType" abstract="true" xbrli:periodType="duration" nillable="true" substitutionGroup="xbrli:item" id="fl_DocumentAndEntityInformationAbstract" />
  <element id="fl_IncreaseDecreaseInFairValueOfHedgePositions" name="IncreaseDecreaseInFairValueOfHedgePositions" nillable="true" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" xbrli:balance="credit" />
  <element id="fl_TwoThousandAndThirteenEmployeeStockPurchasePlanMember" name="TwoThousandAndThirteenEmployeeStockPurchasePlanMember" nillable="true" type="nonnum:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" />
  <element id="fl_ShareBasedCompenstionStockOptionPlansMember" name="ShareBasedCompenstionStockOptionPlansMember" nillable="true" type="nonnum:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" />
  <element id="fl_OsbergVerseFootLockerIncMember" name="OsbergVerseFootLockerIncMember" nillable="true" type="nonnum:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" />
  <element id="fl_LossContingencyLossInPeriodAfterTax" name="LossContingencyLossInPeriodAfterTax" nillable="true" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" xbrli:balance="debit" />
  <element id="fl_AthleticStoresMember" name="AthleticStoresMember" nillable="true" type="nonnum:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" />
  <element id="fl_DirectToCustomerMember" name="DirectToCustomerMember" nillable="true" type="nonnum:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" />
  <element id="fl_AmountOfHedgeGainLossIncludedInAccumulatedOtherComprehensiveIncomeLoss" name="AmountOfHedgeGainLossIncludedInAccumulatedOtherComprehensiveIncomeLoss" nillable="true" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" xbrli:balance="credit" />
  <element id="fl_MinimumPercentageOfCreditAvailabilityToLoanCap" name="MinimumPercentageOfCreditAvailabilityToLoanCap" nillable="true" type="num:percentItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" />
  <element id="fl_MinimumThresholdOfAvailabilityUnderCreditAgreementBeforeCompanyNeedsToComplyWithFinancialCovenants" name="MinimumThresholdOfAvailabilityUnderCreditAgreementBeforeCompanyNeedsToComplyWithFinancialCovenants" nillable="true" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" xbrli:balance="credit" />
</schema>
