Gruppa sendte et videoopptak av drapet til TV-kanalen, opplyste TV-kanalen Al-Jazeera, som ikke kringkastet opptaket.
Gruppa krever at USA løslater irakiske fanger og hadde opprinnelig satt en frist fredag kveld.
Georgi Lazov (30) og Ivailo Kepov (32) forsvant 27. juni. Bulgarske myndigheter har sagt de to bare er vanlige. De arbeidet med å frakte biler fra Bulgaria til Mosul i Nord-Irak, og er ikke politisk involverte. Regjeringen i Sofia sendte diplomater til Irak for å forsøke redde dem.
Bulgaria har 471 soldater i Sør-Irak, med base i Karbala, og den bulgarske regjeringen sier de vil forbli i landet så lenge som nødvendig.
Gruppa som tok de to som gisler skal være ledet av Abu Musab al-Zarqawi,. som anklages av USA for å være Osama bin Ladens mann i Irak og den lokale lederen av al-Qaida-nettverket. Han mistenkes for å organisere motstand mot amerikanske styrker og den USA-innsatte irakiske styret, samt flere halshugginger av utenlandske gisler.