Den algeriske inrikesministern Daho Ould Kabila sade att trupperna hade omringat bostäderna i Amenas, där omkring 20 personer hölls fångna.
Norska, franska, brittiska, amerikanska och japanska medborgare är bland dem.
Ould Kabila sade att militanterna ville lämna Algeriet med gisslan, vilket han inte skulle tillåta.
Tidigare citerade AFP:s nyhetsbyrå en arbetare som sade att militanterna hade krävt att 100 islamistiska fångar skulle friges. En annan rapport sade att de ville att Frankrike skulle avsluta sin militära operation i Mali.
Dussintals algeriska arbetare sades under tiden ha släppts fria.
Gasfältet In Amenas drivs av det algeriska statliga oljebolaget Sonatrach tillsammans med det brittiska oljebolaget BP och Norges Statoil.
Den ligger omkring 1.300 kilometer sydost om huvudstaden, Alger, och omkring 60 kilometer väster om den libyska gränsen.
Vid en nyhetskonferens på onsdagskvällen sade Kabila att en tungt beväpnad "terroristgrupp" med tre fordon hade attackerat en bussförare från In Amenas omkring klockan 05:00 (04:00 GMT).
Förövarna avvisades av polisen som hade eskorterat bussen, men en britt och en algerisk medborgare hade dödats, sade han. Två andra brittiska medborgare, en norsk, två poliser och en säkerhetsvakt skadades också i eldstriden, tillade han.
Efteråt körde militanterna till gasanläggningens bostäder och tog ett antal algeriska och utländska arbetare som gisslan. De hölls i en flygel av bostäderna, som säkerhetstjänsten och armén nu hade omringat, sade Kabila.
"Sedan dess har de vänt sig bort. Säkerhetsstyrkorna befäster sin position runt basen", tillade han. "Det verkar som om [de militanta] vill lämna regionen, lämna landet med gisslan. Detta är helt oacceptabelt för de algeriska myndigheterna."
Ministern sade att gränspassager i närheten hade stängts som en försiktighetsåtgärd och att utrikesministeriet hade kontakt med diplomater från gisslanländerna.
Förenade kungarikets utrikesminister William Hague bekräftade att gisslan inkluderade "ett antal brittiska medborgare", och tillade: "Detta är därför en mycket farlig situation."
Norsk premiärminister Jens Stoltenberg sade att 13 norska anställda i Statoil tros hållas som gisslan vid gasanläggningen.
Amerikanska departementets taleskvinna Victoria Nuland bekräftade att amerikanerna var bland de beslagtagna, medan den irländske utrikesministern Eamon Gilmore sade att en av landets medborgare var gisslan.
Japanska nyhetsbyråer med namnlösa regeringstjänstemän sa att det fanns tre japanska gisslan.
Kabila sade att militanterna var från Algeriet och att de opererade på order av Mokhtar Belmokhtar, en överbefälhavare för al-Qaida i Islamiska Maghreb (AQIM) före slutet av förra året, när han bildade sin egen beväpnade grupp efter att uppenbarligen ha gått ut med andra ledare.
Tidigare sa en man som påstod sig vara talesman för militanterna till BBC Arabiska att al-Qaida hade utfört attacken.
Han hävdade att de hade tillåtit algeriska arbetare att lämna gasanläggningen och endast inneha utländska medborgare.
En lista med krav hade skickats till de algeriska myndigheterna, och gisslan skulle dödas om trupperna försökte rädda dem, tillade talesmannen.
"Det skulle vara lätt för den algeriska militären att storma gaskomplexet, men resultatet av en sådan operation skulle bli katastrofalt", varnade han.
Talare för två grupper som tros ledas av Belmokhtar - Khaled Abu al-Abbas-brigaden och den undertecknade blodbataljonen - sa att de låg bakom incidenten.
Den senare berättade Mauretaniens ANI nyhetsbyrå att den hade tagit mer än 40 gisslan, inklusive sju amerikaner, två franska medborgare och två brittiska medborgare.
"Vi håller de algeriska och franska regeringarna, och gisslanländerna, helt ansvariga för deras långsamhet att uppfylla våra krav, varav främst är ett omedelbart stopp för aggressionen mot våra bröder i Mali", tillade talesmannen.
En av arbetarna sade per telefon till AFP:s nyhetsbyrå att militanterna krävde att 100 islamister skulle friges i Algeriet.
En annan arbetare berättade för tidningen Le Figaro i Frankrike att fångvaktarna hade brutit anläggningen och krävt mat, vatten och fordon.
Militanta grupper har lovat att hämnas Frankrikes militära ingripande i Mali, där dess styrkor har bekämpat islamister kopplade till AQIM under den senaste veckan. Algeriet har tillåtit franska flygplan att använda sitt luftrum.
Islamistiska militanter har attackerat och ockuperat en gasanläggning i Algeriet, dödat en britt och en algerisk och tagit utländska arbetare som gisslan.