Kanadensiska tjänstemän sade att en attack hade planerats med stöd från al-Qaida element i Iran, även om det inte fanns några bevis för statlig sponsring.
Chiheb Esseghaier, 30 år, och Raed Jaser, 35 år, ska inställa sig i domstol på tisdag för en borgensförhandling.
Irans utrikesminister Ali Akbar Salehi sade att föreslå en koppling mellan al-Qaida och Iran var "löjlig".
"Detta är det roligaste jag har hört under mina 64 år," Mr Salehi berättade Iranian Isana nyhetsbyrå.
"Det är verkligen löjligt att länka al-Qaida till Iran. Jag hoppas att de kanadensiska myndigheterna tänker lite mer rationellt och uppmärksammar medvetandet hos folket och den allmänna opinionen i världen."
Al-Qaida - en militant Salafistisk islamisk rörelse - predikar en radikal anti-shia-ideologi som sätter den stadigt i strid med Shia Iran.
Men analytiker säger att trots denna fiendskap har al-Qaida och Iran tolererat varandra där det passar dem.
I september förra året bröt Kanada diplomatiska förbindelser med Iran, stängde sin ambassad i Teheran och drev ut alla kvarvarande iranska diplomater från Kanada.
På den tiden utrikesminister John Baird sade Kanada såg Iran "som det viktigaste hotet mot global fred och säkerhet i världen idag".
De kanadensiska myndigheterna sa att de två misstänkta greps i Montreal och Toronto i måndags. De är inte kanadensiska medborgare, men deras nationaliteter har ännu inte officiellt bekräftats.
Enligt kanadensiska medierapporter är Esseghaier tunisisk medborgare medan Jaser anses vara en palestinsk medborgare i Förenade Arabemiraten.
Kanada's Globe and Mail rapporterade att paret hade varit under utredning sedan förra året efter ett tips av en orolig imam i Toronto Muselman community.
Imam oroade sig för att ungdomar i hans samhälle korrumperades av en extremist, sades det i rapporten.
Det påstås att de två hade planerat att spåra ur ett persontåg i det större Torontoområdet, men det är inte klart när.
Den kungliga kanadensiska Mounted Police (RCMP) sade den övervakning operation som ledde till arresteringarna var "ett resultat av omfattande samarbetsinsatser".
Det stod att FBI-agenter från USA var inblandade i att hjälpa till att omintetgöra attacken, även om en amerikansk justitieminister sa att det inte fanns något samband mellan komplotten och förra veckans bombningar i Boston Marathon.
RCMP sade de två män, som inte var kanadensiska medborgare, hade planerat att spåra ur ett tåg som drivs av VIA Rail och "döda och skada människor".
RCMP Chief Superintendent Jennifer Strachan sade attacken var "definitivt i planeringsstadiet men inte nära förestående".
"Vi hävdar att dessa två individer vidtog åtgärder och genomförde aktiviteter för att inleda en terroristattack", sade hon.
"De tittade på tåg och järnvägar i Greater Toronto-området."
Chief Supt Strachan sa inte om den linje som var föremål för målet var en gränsöverskridande linje med USA.
Men Globe and Mail, som citerade källor, sade att det gällde ett tåg i Toronto-New York, och New York Republikan representant Peter King sade attacken var avsedd "att orsaka betydande förlust av människoliv inklusive New York-bor".
VIA Rail, som bedriver persontrafik över hela Kanada, sade att "på nolltid" var passagerare eller medborgare i överhängande fara.
Den kanadensiske säkerhetsministern Vic Toews sade att arresteringarna visade att terrorismen fortsatte att vara ett verkligt hot mot Kanada.
"Kanada kommer inte att tolerera terroristverksamhet och vi kommer inte att användas som en säker tillflyktsort för terrorister eller dem som stöder terroristverksamhet", sade han i parlamentet.
Analytiker säger att Irans förbindelser med al-Qaida är skuggiga och komplexa.
Några av gruppens ledande personer - däribland Usama Bin Ladins son, Saad Bin Ladin och före detta säkerhetschef Saif al-Adel - sägs ha flytt till Iran efter den USA-ledda invasionen av Afghanistan 2001.
De påstods hållas i husarrest av Irans islamiska revolutionsgard, även om Teheran aldrig erkände deras närvaro.
Enligt USA är Saif al-Adels svärfar Mustafa Hamid länken mellan al-Qaida och den iranska regeringen.
Efter talibanernas fall sägs han ha förhandlat fram en säker omplacering av flera ledande al-Qaida-medlemmar och deras familjer till Iran. I mitten av 2003 arresterades han av de iranska myndigheterna.
Iran har förnekat kopplingar till två män som arresterats i Kanada på grund av misstanke om att ha planerat en attack på ett tåg.