De två männen filmas på arabiska och hänvisar till IS-ledaren Abu Bakr al-Baghdadi. Man har ett papper på vilket IS-flaggan trycks.
Fr Jacques Hamel, 86, fick halsen avskuren i attacken på tisdagen vid en kyrka i en förort till Normandie.
Båda angriparna sköts ihjäl av polisen efter att ha tagit gisslan.
Videon publicerades av Amaq nyhetsbyrå, media armen av IS, som har publicerat gruppens videor och uttalanden i det förflutna.
Det har inte verifierats av franska polisen.
Rapporter på tisdagen sa att männen hade filmat attacken, men det är inte klart var videon som Amaq publicerade spelades in.
Mer om denna berättelse
Vänner minns hjärntvättade Kermiche
Jacques Hamel: Tributer till präst som överlämnade livet åt kyrkan
Vad vi vet om kyrkoangrepp
Frankrike svarar med krav på fred och förståelse
En av de två angriparna har redan utsetts av polisen till Adel Kermiche, 19, som två gånger hade försökt nå Syrien för att ansluta sig till IS.
Franska utredare tror att de är nära att identifiera den andra angriparen, enligt franska media rapporter.
Officerare sägs ha hittat ett ID-kort hemma hos Kermiche som tillhör en person som heter Abdelmalik P, från Aix-les-Bains i östra Frankrike.
Det är inte känt om detta är den andra angriparen, vars ansikte var svårt vanställt av polisen skjuta.
Den franska tidningen Le Monde rapporterar också att franska säkerhetstjänstemän fick ett tips på fredag från en okänd utländsk underrättelsepartner om att en person planerade en attack under de kommande dagarna.
Tidningen säger att ett fotografi av individen gavs men ingen identitet, och den franska polisen jagade mannen i upptakten till attacken.
Det kan vara att den hittills oidentifierade mannen är den döda andra angriparen, BBC: s Hugh Schofield i Paris säger.
Ett antal medier i Frankrike har meddelat att de inte längre kommer att publicera bilder av personer som är ansvariga för terrorattacker.
I en ledarartikel sade Le Monde att man gjorde detta "för att undvika att ge eftertrycklig kredit" till de ansvariga, samtidigt som man tillade att avsikten med att döda Fader Hamel var att provocera fram "den blinda hämnd som skulle placera hela landet under imperium av hat".
Flytten upprepades av programföretagen BFMTV, Frankrike 24 och RFI.
Ett uttalande av den gemensamma redaktionen i France 24 och RFI sade att de var "medvetna om ekot som erbjuds av våra antenner... till terroriströrelser som hävdar en stat som inte existerar".
Den katolska dagstidningen La Croix, som sade att den följde efter, sade i sin ledare på onsdag att "att reagera på hat med hat skulle innebära att ondskan har segrat". Tidningen skulle nu bara ge förnamn på angripare, sägs det.
Den europeiska radiostationen meddelade att den inte skulle nämna förövarna av terrorattacker.
Mordet i Normandie kom 12 dagar efter lastbilsattacken i Nice där 84 personer dog. Mördaren i Nice lovade också IS lojalitet.
Tidigare på onsdagen krävde franska religiösa ledare större säkerhet på platser för tillbedjan över hela landet.
Representanter för kristna, muslimska, judiska och buddistiska religioner talade efter att ha träffat president Francois Hollande.
Hollande deltog också i en mässa för Fr Hamel i Notre Dame-katedralen i Paris.
Den så kallade islamiska staten (IS) har släppt en video där det står att två män som mördade en präst i Frankrike, lovar trohet till gruppen.