-----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,
 JnTLYSFpeQYPHAbhwvsUQR9cr1NBJ09of5h9spSwl6n4rFnF9u+oaC30q/Bj7eyg
 T+3wwCoDjFEq8JbYMQkB1A==

<SEC-DOCUMENT>0001179110-06-000828.txt : 20060106
<SEC-HEADER>0001179110-06-000828.hdr.sgml : 20060106
<ACCEPTANCE-DATETIME>20060106135342
ACCESSION NUMBER:		0001179110-06-000828
CONFORMED SUBMISSION TYPE:	4
PUBLIC DOCUMENT COUNT:		1
CONFORMED PERIOD OF REPORT:	20060105
FILED AS OF DATE:		20060106
DATE AS OF CHANGE:		20060106

REPORTING-OWNER:	

	OWNER DATA:	
		COMPANY CONFORMED NAME:			Bryja James J
		CENTRAL INDEX KEY:			0001305781

	FILING VALUES:
		FORM TYPE:		4
		SEC ACT:		1934 Act
		SEC FILE NUMBER:	001-32331
		FILM NUMBER:		06515863

	BUSINESS ADDRESS:	
		BUSINESS PHONE:		410 689 7500

	MAIL ADDRESS:	
		STREET 1:		999 CORPORATE BOULEVARD
		STREET 2:		SUITE 300
		CITY:			LINTHICUM HEIGHTS
		STATE:			MD
		ZIP:			21090

ISSUER:		

	COMPANY DATA:	
		COMPANY CONFORMED NAME:			Foundation Coal Holdings, Inc.
		CENTRAL INDEX KEY:			0001301063
		STANDARD INDUSTRIAL CLASSIFICATION:	BITUMINOUS COAL & LIGNITE SURFACE MINING [1221]
		IRS NUMBER:				421638663
		STATE OF INCORPORATION:			DE
		FISCAL YEAR END:			1231

	BUSINESS ADDRESS:	
		STREET 1:		999 CORPORATE BOULEVARD, SUITE 300
		CITY:			LINTHICUM
		STATE:			MD
		ZIP:			21090-2227
		BUSINESS PHONE:		410-689-7500

	MAIL ADDRESS:	
		STREET 1:		999 CORPORATE BOULEVARD, SUITE 300
		CITY:			LINTHICUM
		STATE:			MD
		ZIP:			21090-2227
</SEC-HEADER>
<DOCUMENT>
<TYPE>4
<SEQUENCE>1
<FILENAME>edgar.xml
<DESCRIPTION>FORM 4 -
<TEXT>
<XML>
<?xml version="1.0"?>
<ownershipDocument>

    <schemaVersion>X0202</schemaVersion>

    <documentType>4</documentType>

    <periodOfReport>2006-01-05</periodOfReport>

    <notSubjectToSection16>0</notSubjectToSection16>

    <issuer>
        <issuerCik>0001301063</issuerCik>
        <issuerName>Foundation Coal Holdings, Inc.</issuerName>
        <issuerTradingSymbol>FCL</issuerTradingSymbol>
    </issuer>

    <reportingOwner>
        <reportingOwnerId>
            <rptOwnerCik>0001305781</rptOwnerCik>
            <rptOwnerName>Bryja James J</rptOwnerName>
        </reportingOwnerId>
        <reportingOwnerAddress>
            <rptOwnerStreet1>999 CORPORATE BOULEVARD</rptOwnerStreet1>
            <rptOwnerStreet2>SUITE 300</rptOwnerStreet2>
            <rptOwnerCity>LINTHICUM HEIGHTS</rptOwnerCity>
            <rptOwnerState>MD</rptOwnerState>
            <rptOwnerZipCode>21090-2227</rptOwnerZipCode>
            <rptOwnerStateDescription></rptOwnerStateDescription>
        </reportingOwnerAddress>
        <reportingOwnerRelationship>
            <isDirector>0</isDirector>
            <isOfficer>1</isOfficer>
            <isTenPercentOwner>0</isTenPercentOwner>
            <isOther>0</isOther>
            <officerTitle>SVP, Eastern Operatons</officerTitle>
            <otherText></otherText>
        </reportingOwnerRelationship>
    </reportingOwner>

    <nonDerivativeTable>
        <nonDerivativeTransaction>
            <securityTitle>
                <value>Common Stock</value>
            </securityTitle>
            <transactionDate>
                <value>2006-01-05</value>
            </transactionDate>
            <transactionCoding>
                <transactionFormType>4</transactionFormType>
                <transactionCode>M</transactionCode>
                <equitySwapInvolved>0</equitySwapInvolved>
                <footnoteId id="F1"/>
            </transactionCoding>
            <transactionAmounts>
                <transactionShares>
                    <value>1473</value>
                </transactionShares>
                <transactionPricePerShare>
                    <value>4.87</value>
                </transactionPricePerShare>
                <transactionAcquiredDisposedCode>
                    <value>A</value>
                </transactionAcquiredDisposedCode>
            </transactionAmounts>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>51245</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>D</value>
                </directOrIndirectOwnership>
            </ownershipNature>
        </nonDerivativeTransaction>
        <nonDerivativeTransaction>
            <securityTitle>
                <value>Common Stock</value>
            </securityTitle>
            <transactionDate>
                <value>2006-01-05</value>
            </transactionDate>
            <transactionCoding>
                <transactionFormType>4</transactionFormType>
                <transactionCode>M</transactionCode>
                <equitySwapInvolved>0</equitySwapInvolved>
                <footnoteId id="F1"/>
            </transactionCoding>
            <transactionAmounts>
                <transactionShares>
                    <value>7000</value>
                </transactionShares>
                <transactionPricePerShare>
                    <value>8.53</value>
                </transactionPricePerShare>
                <transactionAcquiredDisposedCode>
                    <value>A</value>
                </transactionAcquiredDisposedCode>
            </transactionAmounts>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>58245</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>D</value>
                </directOrIndirectOwnership>
            </ownershipNature>
        </nonDerivativeTransaction>
        <nonDerivativeTransaction>
            <securityTitle>
                <value>Common Stock</value>
            </securityTitle>
            <transactionDate>
                <value>2006-01-05</value>
            </transactionDate>
            <transactionCoding>
                <transactionFormType>4</transactionFormType>
                <transactionCode>S</transactionCode>
                <equitySwapInvolved>0</equitySwapInvolved>
                <footnoteId id="F1"/>
            </transactionCoding>
            <transactionAmounts>
                <transactionShares>
                    <value>14073</value>
                </transactionShares>
                <transactionPricePerShare>
                    <value>40.3101</value>
                    <footnoteId id="F2"/>
                </transactionPricePerShare>
                <transactionAcquiredDisposedCode>
                    <value>D</value>
                </transactionAcquiredDisposedCode>
            </transactionAmounts>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>44172</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>D</value>
                </directOrIndirectOwnership>
            </ownershipNature>
        </nonDerivativeTransaction>
    </nonDerivativeTable>

    <derivativeTable>
        <derivativeTransaction>
            <securityTitle>
                <value>Non-Qualified Stock Option (right to buy)</value>
            </securityTitle>
            <conversionOrExercisePrice>
                <value>4.87</value>
            </conversionOrExercisePrice>
            <transactionDate>
                <value>2006-01-05</value>
            </transactionDate>
            <transactionCoding>
                <transactionFormType>4</transactionFormType>
                <transactionCode>M</transactionCode>
                <equitySwapInvolved>0</equitySwapInvolved>
            </transactionCoding>
            <transactionAmounts>
                <transactionShares>
                    <value>1473</value>
                </transactionShares>
                <transactionPricePerShare>
                    <value>0</value>
                </transactionPricePerShare>
                <transactionAcquiredDisposedCode>
                    <value>D</value>
                </transactionAcquiredDisposedCode>
            </transactionAmounts>
            <exerciseDate>
                <footnoteId id="F3"/>
            </exerciseDate>
            <expirationDate>
                <value>2014-08-10</value>
            </expirationDate>
            <underlyingSecurity>
                <underlyingSecurityTitle>
                    <value>Common Stock</value>
                </underlyingSecurityTitle>
                <underlyingSecurityShares>
                    <value>1473</value>
                </underlyingSecurityShares>
            </underlyingSecurity>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>73676</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>D</value>
                </directOrIndirectOwnership>
            </ownershipNature>
        </derivativeTransaction>
        <derivativeTransaction>
            <securityTitle>
                <value>Non-Qualified Stock Option (right to buy)</value>
            </securityTitle>
            <conversionOrExercisePrice>
                <value>8.53</value>
            </conversionOrExercisePrice>
            <transactionDate>
                <value>2006-01-05</value>
            </transactionDate>
            <transactionCoding>
                <transactionFormType>4</transactionFormType>
                <transactionCode>M</transactionCode>
                <equitySwapInvolved>0</equitySwapInvolved>
            </transactionCoding>
            <transactionAmounts>
                <transactionShares>
                    <value>7000</value>
                </transactionShares>
                <transactionPricePerShare>
                    <value>0</value>
                </transactionPricePerShare>
                <transactionAcquiredDisposedCode>
                    <value>D</value>
                </transactionAcquiredDisposedCode>
            </transactionAmounts>
            <exerciseDate>
                <footnoteId id="F4"/>
            </exerciseDate>
            <expirationDate>
                <value>2014-08-10</value>
            </expirationDate>
            <underlyingSecurity>
                <underlyingSecurityTitle>
                    <value>Common stock</value>
                </underlyingSecurityTitle>
                <underlyingSecurityShares>
                    <value>7000</value>
                </underlyingSecurityShares>
            </underlyingSecurity>
            <postTransactionAmounts>
                <sharesOwnedFollowingTransaction>
                    <value>232446</value>
                </sharesOwnedFollowingTransaction>
            </postTransactionAmounts>
            <ownershipNature>
                <directOrIndirectOwnership>
                    <value>D</value>
                </directOrIndirectOwnership>
            </ownershipNature>
        </derivativeTransaction>
    </derivativeTable>

    <footnotes>
        <footnote id="F1">The transactions reported in this Form 4 were effected pursuant to a Rule 10b5-1 trading plan adopted by the reporting person on September 19, 2005.</footnote>
        <footnote id="F2">Represents average sales price of $40.3101 with sales prices ranging from $40.10 to $40.36.</footnote>
        <footnote id="F3">The 92,095 shares of common stock originally subject to this option vest in five equal installments beginning on December 31, 2004.</footnote>
        <footnote id="F4">The 239,446 shares of common stock originally subject to this option will vest on August 10, 2012.  However, each calendar year through December 31, 2008, and upon the achievement of certain annual performance targets, the options are subject to partial accelerated vesting.  The Compensation Committee approved the vesting of ten percent of the options effective December 31, 2004.</footnote>
    </footnotes>

    <ownerSignature>
        <signatureName>/s/ Edythe C. Katz, Attorney in Fact</signatureName>
        <signatureDate>2006-01-06</signatureDate>
    </ownerSignature>
</ownershipDocument>
</XML>
</TEXT>
</DOCUMENT>
</SEC-DOCUMENT>
-----END PRIVACY-ENHANCED MESSAGE-----