James Lynch, talesman för FN:s flyktingbyrå (UNHCR), berättade för BBC att passagerare såg smugglare betalas efter att båten avlyssnats.
Australisk premiärminister Tony Abbott på fredag medgav med hjälp av "kreativa" strategier för att stoppa migrerande båtar men vägrade att gå in i detalj.
Landets invandrings- och utrikesministrar nekades betalningar.
"Den båt som räddades av den indonesiska flottan den 31 maj - vi har intervjuat 65 passagerare och de har sagt att besättningen fick en betalning," sade Lynch.
Han sade att passagerarna - 54 från Sri Lanka, 10 från Bangladesh och en från Myanmar - förflyttades till en tullbåt i fyra dagar "innan de sattes på två båtar och skickades tillbaka till Indonesien".
Han tillade: "Mr Abbott säger att anledningen är att rädda liv eftersom människor riskerar sina liv på båtarna, och jag håller med, men jag är inte säker på att sätta dem tillbaka på båtar och skicka tillbaka dem är svaret."
Lynch sade att Australien hade ett ansvar enligt FN-fördragen, som man hade undertecknat, för att se om någon av migranterna behövde internationellt skydd.
Han anklagade Australien för att "skicka fel signal" till andra länder i regionen - inklusive Myanmar, Indonesien, Malaysia och Thailand - som FN försöker övertyga om att tillåta migranter att gå i land.
Indonesiens utrikesministerium sa att det var "mycket oroat" över den påstådda betalningen.
Den indonesiska flottan sade att den snappade upp båtarna när de återvände och arresterade besättningen, som sade att de hade fått 5 000 dollar vardera (3 900 dollar; 2 500 pund) för att vända tillbaka.
Lokal polischef Hidayat sa till AFP nyhetsbyrå: "Jag såg pengarna med egna ögon."
När Abbott talade med Radio 3AW på fredagsmorgonen vägrade han att förneka att en betalning hade gjorts och sade helt enkelt att "kreativa strategier" hade utvecklats för att stoppa de migrerande båtarna.
"Vi har stoppat handeln och vi kommer att göra vad vi måste för att se till att det stannar," sade han.
Enligt Australiens kontroversiella politik tillåts inga invandrare och asylsökande att nå sina territorier med båt. I stället fångas de upp till havs och förs tillbaka eller förs till häkten på ön Nauru och på Manusön i Papua Nya Guinea.
Australien asyl: Varför är det kontroversiellt?
Migranter på en båt på väg mot Australien har sagt till FN att besättningen fick betalt av den australiska flottan för att återvända.