-----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,
 IIsS49X4MgClhmfglFw6Hc4MkOZg4QEFnbxY7967Wt6YlyMST9FeuBbsZiLWdNO8
 PDc0fOlzfEjJhip+ecCxTw==

<SEC-DOCUMENT>0001209191-08-037550.txt : 20080617
<SEC-HEADER>0001209191-08-037550.hdr.sgml : 20080617
<ACCEPTANCE-DATETIME>20080617161201
ACCESSION NUMBER:		0001209191-08-037550
CONFORMED SUBMISSION TYPE:	4
PUBLIC DOCUMENT COUNT:		1
CONFORMED PERIOD OF REPORT:	20080403
FILED AS OF DATE:		20080617
DATE AS OF CHANGE:		20080617

ISSUER:		

	COMPANY DATA:	
		COMPANY CONFORMED NAME:			Horsehead Holding Corp
		CENTRAL INDEX KEY:			0001385544
		STANDARD INDUSTRIAL CLASSIFICATION:	PRIMARY SMELTING & REFINING OF NONFERROUS METALS [3330]
		IRS NUMBER:				000000000

	BUSINESS ADDRESS:	
		STREET 1:		4955 STEUBENVILLE PIKE
		STREET 2:		SUITE 405
		CITY:			PITTSBURGH
		STATE:			PA
		ZIP:			15205
		BUSINESS PHONE:		724-773-2212

	MAIL ADDRESS:	
		STREET 1:		4955 STEUBENVILLE PIKE
		STREET 2:		SUITE 405
		CITY:			PITTSBURGH
		STATE:			PA
		ZIP:			15205

REPORTING-OWNER:	

	OWNER DATA:	
		COMPANY CONFORMED NAME:			SCHERICH ROBERT D
		CENTRAL INDEX KEY:			0001216622

	FILING VALUES:
		FORM TYPE:		4
		SEC ACT:		1934 Act
		SEC FILE NUMBER:	001-33658
		FILM NUMBER:		08903341

	BUSINESS ADDRESS:	
		STREET 1:		VALLEY NATIONAL GASES INC
		STREET 2:		200 WEST BEAU STREET SUITE 200
		CITY:			WASHINGTON
		STATE:			PA
		ZIP:			15301
		BUSINESS PHONE:		7242283000
</SEC-HEADER>
<DOCUMENT>
<TYPE>4
<SEQUENCE>1
<FILENAME>doc4.xml
<DESCRIPTION>FORM 4 SUBMISSION
<TEXT>
<XML>
<?xml version="1.0"?>
<ownershipDocument>

    <schemaVersion>X0202</schemaVersion>

    <documentType>4</documentType>

    <periodOfReport>2008-04-03</periodOfReport>

    <notSubjectToSection16>0</notSubjectToSection16>

    <issuer>
        <issuerCik>0001385544</issuerCik>
        <issuerName>Horsehead Holding Corp</issuerName>
        <issuerTradingSymbol>ZINC</issuerTradingSymbol>
    </issuer>

    <reportingOwner>
        <reportingOwnerId>
            <rptOwnerCik>0001216622</rptOwnerCik>
            <rptOwnerName>SCHERICH ROBERT D</rptOwnerName>
        </reportingOwnerId>
        <reportingOwnerAddress>
            <rptOwnerStreet1>4955 STEUBENVILLE PIKE</rptOwnerStreet1>
            <rptOwnerStreet2>SUITE 405</rptOwnerStreet2>
            <rptOwnerCity>PITTSBURGH</rptOwnerCity>
            <rptOwnerState>PA</rptOwnerState>
            <rptOwnerZipCode>15205</rptOwnerZipCode>
            <rptOwnerStateDescription></rptOwnerStateDescription>
        </reportingOwnerAddress>
        <reportingOwnerRelationship>
            <isDirector>0</isDirector>
            <isOfficer>1</isOfficer>
            <isTenPercentOwner>0</isTenPercentOwner>
            <isOther>0</isOther>
            <officerTitle>VP &amp; CFO</officerTitle>
        </reportingOwnerRelationship>
    </reportingOwner>

    <nonDerivativeTable>
        <nonDerivativeTransaction>
            <securityTitle>
                <value>Common Stock, par value $0.01 per share</value>
            </securityTitle>
            <transactionDate>
                <value>2008-04-03</value>
            </transactionDate>
            <deemedExecutionDate></deemedExecutionDate>
            <transactionCoding>
                <transactionFormType>4</transactionFormType>
                <transactionCode>A</transactionCode>
                <equitySwapInvolved>0</equitySwapInvolved>
            </transactionCoding>
            <transactionTimeliness>
                <value></value>
            </transactionTimeliness>
            <transactionAmounts>
                <transactionShares>
                    <value>12500</value>
                    <footnoteId id="F1"/>
                </transactionShares>
                <transactionPricePerShare>
                    <value>0.01</value>
                </transactionPricePerShare>
                <transactionAcquiredDisposedCode>
                    <value>A</value>
                </transactionAcquiredDisposedCode>
            </transactionAmounts>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>12500</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>D</value>
                </directOrIndirectOwnership>
            </ownershipNature>
        </nonDerivativeTransaction>
    </nonDerivativeTable>

    <footnotes>
        <footnote id="F1">Represents 12,500 restricted stock units of the Reporting Person, which are subject to vesting.  Upon vesting, the Reporting Person shall be entitled to receive a number shares of common stock equal to the number of restricted stock units then vesting.  One third of the restricted stock units will vest on each of April 3, 2011, 2012 and 2013.</footnote>
    </footnotes>

    <remarks></remarks>

    <ownerSignature>
        <signatureName>/s/ Robert D. Scherich</signatureName>
        <signatureDate>2008-06-17</signatureDate>
    </ownerSignature>
</ownershipDocument>
</XML>
</TEXT>
</DOCUMENT>
</SEC-DOCUMENT>
-----END PRIVACY-ENHANCED MESSAGE-----