Ayatollah Khamenei hyllade trots sina meningsskiljaktigheter ett "stridskompanjon" och sade att detta var en "svår" förlust.
President Hassan Rouhani lovordade Rafsanjani som en stor man i den islamiska revolutionen.
Regeringen har tillkännagett tre dagars sorg, vilket gör tisdagen till en allmän helgdag för hans begravning i Teheran.
Rafsanjani, som tjänstgjorde som president 1989-1997, var avgörande i 1979 års revolution. Men senare i livet blev han en motvikt mot de konservativa.
"De olika åsikterna och tolkningarna under denna långa period kunde aldrig helt bryta upp vänskapen mellan oss", säger Ayatollah Khamenei.
Mr Rafsanjani dog på söndagen på ett sjukhus i Teheran efter en hjärtattack.
Hans kropp fördes till Jamarans bönesal, residenset för Islamiska republikens grundare, Ayatollah Rohullah Khomeini, där släktingar, politiker och religiösa personer samlades för att visa sin sista aktning.
Rafsanjani hade varit mentor till president Rouhani, som han stödde efter sitt eget försök att ställa upp i 2013 års val som reformistkandidat, förkastades av det mäktiga Guardian Council.
Rouhani sade på Twitter: "Revolutionens store mans själ, symbolen för tålamod och motstånd, har kommit till Himlen."
Analytiker säger att Rafsanjanis plötsliga död är ett stort slag mot presidenten, som förbereder sig för omval i maj.
Iranska tidningar över hela det politiska spektrumet hyllar Rafsanjani. De flesta framsidor är stänkta med bilder och bildtexter som belyser hans centrala roll i Irans politik. Många har använt svart som bakgrund.
"Iran sörjer modern Amir Kabirs död", säger moderat Arman-e Emruz och jämför Rafsanjani med den man som allmänt anses vara Irans förste reformator och moderniserare.
En "orolig förlust", måttlig daglig Iran klagar, medan reformisten Aftab-e Yazd, under en bild av Rafsanjanis sörjande barn, bekräftar att "Iran sörjer".
Till och med hårdnackade dailies är med på lovorden. Javan noterar sin närhet till den islamiska republikens grundare, Ayatollah Ruhollah Khomeini, och den högste ledaren Ali Khamenei i sin rubrik: "Man med tuffa dagar av strider och vän till Imam och ledaren rusar för att möta Gud."
Hard-line Vatan-e Emrooz beskriver honom som "en av pelarna" och "en äkta figur" av Irans islamiska revolution.
BBC Övervakning rapporterar och analyserar nyheter från TV, radio, webb och tryckta medier runt om i världen. Du kan följa BBC Monitoring på Twitter och Facebook.
BBC Persiska Kasra Naji säger Mr Rafsanjani var en stor överlevare av den iranska revolutionen, alltid lyckas hålla sig flytande i den ändlösa politiska kampen mellan de hårdföra och de moderata, kvarvarande inflytelserika.
Under de senaste åren, säger vår korrespondent, har han varit en central person i reformrörelsen som har försökt ha ett modererande inflytande på Iran och Ayatollah Khamenei.
Rafsanjanis sista roll var chef för rådet (expedition) som försöker lösa tvister mellan parlamentet och Guardian Council.
Akbar Hashemi Rafsanjani föddes 1934 i sydöstra Iran till en familj av bönder.
Han studerade teologi i den heliga staden Qom med Ayatollah Ruhollah Khomeini - som fortsatte att leda den islamiska revolutionen 1979 - och fängslades flera gånger under shahen.
Under det sista året av kriget mellan 1980 och88 mot Irak utnämnde Ayatollah Khomeini honom till tillförordnad chef för de väpnade styrkorna.
Han betraktades som den främsta drivkraften bakom Irans godtagande av FN:s säkerhetsråds resolution som avslutade kriget.
Rafsanjani var också en viktig aktör i utvecklingen av Irans kärntekniska program och gav nyligen starkt stöd till den banbrytande kärnkraftsaffären 2015 med världsmakter.
Han var en man känd för ett skarpsinnigt förstånd men som också kunde vara hänsynslös.
Han förespråkade en progressiv ekonomisk politik, uppmuntrar privata företag och förbättrar infrastrukturen. Hans egna affärsinnehav rapporterades vara utbrett.
Rafsanjani var ordförande för tredje gången 2005 men förlorade till Mahmoud Ahmadinejad.
Rafsanjani blev öppet kritisk mot den segerrike presidenten och 2009 ställde han sig på reformatorernas sida som ifrågasatte det årets val. Trots detta vann Ahmadinejad en andra mandatperiod.
Rafsanjani fortsatte att kämpa för måttliga orsaker, såsom frigivning av politiska fångar och större politiska friheter för partier som var beredda att arbeta inom konstitutionen.
Några av medlemmarna i Rafsanjanis familj har också gjort rubrikerna. Hans dotter Faezeh Hashemi lockade irret av hårda liners när hon träffade en ledare för Bahai religiösa minoritet - som Irans ledarskap betraktar som en kättersk sekt - förra året.
Och hans son Mehdi Hashemi Rafsanjani fängslades 2015 efter att ha dömts för "säkerhetsbrott och ekonomiska brott".
Irans högste ledare Ayatollah Ali Khamenei har lett hyllningar till före detta president Akbar Hashemi Rafsanjani, som har dött vid 82 års ålder.