-----BEGIN PRIVACY-ENHANCED MESSAGE-----
Proc-Type: 2001,MIC-CLEAR
Originator-Name: webmaster@www.sec.gov
Originator-Key-Asymmetric:
 MFgwCgYEVQgBAQICAf8DSgAwRwJAW2sNKK9AVtBzYZmr6aGjlWyK3XmZv3dTINen
 TWSM7vrzLADbmYQaionwg5sDW3P6oaM5D3tdezXMm7z1T+B+twIDAQAB
MIC-Info: RSA-MD5,RSA,
 KJvKUML1J6Vo+AH9ci30wpttm5pahdYbekXqPhKx4YRroZikVVjZLj8TXiSo3E+X
 aNrYAyj+XBinQh8FFydYNg==

<SEC-DOCUMENT>0000935703-04-000151.txt : 20041209
<SEC-HEADER>0000935703-04-000151.hdr.sgml : 20041209
<ACCEPTANCE-DATETIME>20041209165953
ACCESSION NUMBER:		0000935703-04-000151
CONFORMED SUBMISSION TYPE:	4
PUBLIC DOCUMENT COUNT:		1
CONFORMED PERIOD OF REPORT:	20041104
FILED AS OF DATE:		20041209
DATE AS OF CHANGE:		20041209

ISSUER:		

	COMPANY DATA:	
		COMPANY CONFORMED NAME:			DOLLAR TREE STORES INC
		CENTRAL INDEX KEY:			0000935703
		STANDARD INDUSTRIAL CLASSIFICATION:	RETAIL-VARIETY STORES [5331]
		IRS NUMBER:				541387365
		STATE OF INCORPORATION:			VA
		FISCAL YEAR END:			1231

	BUSINESS ADDRESS:	
		STREET 1:		500 VOLVO PARKWAY
		STREET 2:		N/A
		CITY:			CHESAPEAKE
		STATE:			VA
		ZIP:			23320
		BUSINESS PHONE:		(757) 321-5000

	MAIL ADDRESS:	
		STREET 1:		500 VOLVO PARKWAY
		CITY:			CHESAPEAKE
		STATE:			VA
		ZIP:			23320

REPORTING-OWNER:	

	OWNER DATA:	
		COMPANY CONFORMED NAME:			PERRY J DOUGLAS
		CENTRAL INDEX KEY:			0001009270

	FILING VALUES:
		FORM TYPE:		4
		SEC ACT:		1934 Act
		SEC FILE NUMBER:	000-25464
		FILM NUMBER:		041193908

	BUSINESS ADDRESS:	
		BUSINESS PHONE:		7573215000

	MAIL ADDRESS:	
		STREET 1:		500 VOLVO PARKWAY
		CITY:			CHESAPEAKE
		STATE:			VA
		ZIP:			23320
</SEC-HEADER>
<DOCUMENT>
<TYPE>4
<SEQUENCE>1
<FILENAME>primary_doc.xml
<DESCRIPTION>PRIMARY DOCUMENT
<TEXT>
<XML>
<?xml version="1.0"?>
<ownershipDocument>

    <schemaVersion>X0202</schemaVersion>

    <documentType>4</documentType>

    <periodOfReport>2004-11-04</periodOfReport>

    <notSubjectToSection16>0</notSubjectToSection16>

    <issuer>
        <issuerCik>0000935703</issuerCik>
        <issuerName>DOLLAR TREE STORES INC</issuerName>
        <issuerTradingSymbol>DLTR</issuerTradingSymbol>
    </issuer>

    <reportingOwner>
        <reportingOwnerId>
            <rptOwnerCik>0001009270</rptOwnerCik>
            <rptOwnerName>PERRY J DOUGLAS</rptOwnerName>
        </reportingOwnerId>
        <reportingOwnerAddress>
            <rptOwnerStreet1>500 VOLVO PARKWAY</rptOwnerStreet1>
            <rptOwnerStreet2></rptOwnerStreet2>
            <rptOwnerCity>CHESAPEAKE</rptOwnerCity>
            <rptOwnerState>VA</rptOwnerState>
            <rptOwnerZipCode>23320</rptOwnerZipCode>
            <rptOwnerStateDescription></rptOwnerStateDescription>
        </reportingOwnerAddress>
        <reportingOwnerRelationship>
            <isDirector>1</isDirector>
            <isOfficer>0</isOfficer>
            <isTenPercentOwner>0</isTenPercentOwner>
            <isOther>0</isOther>
        </reportingOwnerRelationship>
    </reportingOwner>

    <nonDerivativeTable>
        <nonDerivativeTransaction>
            <securityTitle>
                <value>Common stock</value>
            </securityTitle>
            <transactionDate>
                <value>2004-11-04</value>
            </transactionDate>
            <transactionCoding>
                <transactionFormType>5</transactionFormType>
                <transactionCode>W</transactionCode>
                <equitySwapInvolved>0</equitySwapInvolved>
                <footnoteId id="F1"/>
            </transactionCoding>
            <transactionTimeliness>
                <value>E</value>
            </transactionTimeliness>
            <transactionAmounts>
                <transactionShares>
                    <value>60750</value>
                </transactionShares>
                <transactionPricePerShare>
                    <footnoteId id="F1"/>
                </transactionPricePerShare>
                <transactionAcquiredDisposedCode>
                    <value>A</value>
                </transactionAcquiredDisposedCode>
            </transactionAmounts>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>60750</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>I</value>
                    <footnoteId id="F4"/>
                </directOrIndirectOwnership>
                <natureOfOwnership>
                    <value>Survivor's Trust, of which insider is co-trustee</value>
                </natureOfOwnership>
            </ownershipNature>
        </nonDerivativeTransaction>
        <nonDerivativeTransaction>
            <securityTitle>
                <value>Common stock</value>
            </securityTitle>
            <transactionDate>
                <value>2004-12-08</value>
            </transactionDate>
            <transactionCoding>
                <transactionFormType>4</transactionFormType>
                <transactionCode>S</transactionCode>
                <equitySwapInvolved>0</equitySwapInvolved>
            </transactionCoding>
            <transactionTimeliness>
                <value></value>
            </transactionTimeliness>
            <transactionAmounts>
                <transactionShares>
                    <value>225000</value>
                </transactionShares>
                <transactionPricePerShare>
                    <value>28.5074</value>
                    <footnoteId id="F3"/>
                </transactionPricePerShare>
                <transactionAcquiredDisposedCode>
                    <value>D</value>
                </transactionAcquiredDisposedCode>
            </transactionAmounts>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>911246</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>I</value>
                    <footnoteId id="F4"/>
                </directOrIndirectOwnership>
                <natureOfOwnership>
                    <value>Trusts (Descendants')</value>
                </natureOfOwnership>
            </ownershipNature>
        </nonDerivativeTransaction>
        <nonDerivativeTransaction>
            <securityTitle>
                <value>Common stock</value>
            </securityTitle>
            <transactionDate>
                <value>2004-12-09</value>
            </transactionDate>
            <transactionCoding>
                <transactionFormType>4</transactionFormType>
                <transactionCode>S</transactionCode>
                <equitySwapInvolved>0</equitySwapInvolved>
            </transactionCoding>
            <transactionTimeliness>
                <value></value>
            </transactionTimeliness>
            <transactionAmounts>
                <transactionShares>
                    <value>66800</value>
                </transactionShares>
                <transactionPricePerShare>
                    <value>28.3823</value>
                    <footnoteId id="F2"/>
                </transactionPricePerShare>
                <transactionAcquiredDisposedCode>
                    <value>D</value>
                </transactionAcquiredDisposedCode>
            </transactionAmounts>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>132000</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>I</value>
                    <footnoteId id="F4"/>
                </directOrIndirectOwnership>
                <natureOfOwnership>
                    <value>2002 GRAT (JDP)</value>
                </natureOfOwnership>
            </ownershipNature>
        </nonDerivativeTransaction>
        <nonDerivativeHolding>
            <securityTitle>
                <value>Common stock</value>
            </securityTitle>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>866964</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>D</value>
                </directOrIndirectOwnership>
            </ownershipNature>
        </nonDerivativeHolding>
        <nonDerivativeHolding>
            <securityTitle>
                <value>Common stock</value>
            </securityTitle>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>110000</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>I</value>
                    <footnoteId id="F4"/>
                </directOrIndirectOwnership>
                <natureOfOwnership>
                    <value>Spouse</value>
                </natureOfOwnership>
            </ownershipNature>
        </nonDerivativeHolding>
        <nonDerivativeHolding>
            <securityTitle>
                <value>Common stock</value>
            </securityTitle>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>10000</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>I</value>
                    <footnoteId id="F4"/>
                </directOrIndirectOwnership>
                <natureOfOwnership>
                    <value>2002 GRAT (PWP)</value>
                </natureOfOwnership>
            </ownershipNature>
        </nonDerivativeHolding>
    </nonDerivativeTable>

    <footnotes>
        <footnote id="F1">Transfer of trust assets from decedent's estate.</footnote>
        <footnote id="F2">Average price of multiple related transactions. All trades, details of which have been reported to the issuer, occurred on this date with prices ranging from $28.31 to $28.45.</footnote>
        <footnote id="F3">Average price of multiple related transactions. All trades, details of which have been reported to the issuer, occurred on this date with prices ranging from $28.25 to $28.65.</footnote>
        <footnote id="F4">Disclaimer: Reporting person disclaims beneficial ownership of all indirectly held securities and this report shall not be deemed an admission that the reporting person is the beneficial owner of such securities for purposes of Section 16 or any other purpose.</footnote>
    </footnotes>

    <ownerSignature>
        <signatureName>Frederick C. Coble, attorney-in-fact</signatureName>
        <signatureDate>2004-12-09</signatureDate>
    </ownerSignature>
</ownershipDocument>

</XML>
</TEXT>
</DOCUMENT>
</SEC-DOCUMENT>
-----END PRIVACY-ENHANCED MESSAGE-----