What were the previous births of Arjun ?
Arjuna was Nara in his former birth.
"Mahadeva said, 'Thou wert in thy former life Nara, the friend of Narayana. In Vadari wert thou engaged in fierce ascetic austerities for several thousands of years. In thee as well as in Vishnu--that first of male beings--dwelleth great might.
Even Bhishma told this to Duryodhana in the Kuru assembly.
It hath been heard by us that the two heroic and mighty car-warriors, Vasudeva and Arjuna, that are now united with each other, are those same ancient gods, the divine Nara and Narayana. Amongst all on earth they are incapable of being vanquished by the Asuras and the gods headed by Indra himself. That Narayana is Krishna, and that Nara is Falguna. Indeed, they are one Soul born in twain. These two, by their acts, enjoy numerous eternal and inexhaustible regions, and are repeatedly born in those worlds when destructive wars are necessary.
When Karna succeded in baffling Arjuna's arrows, Krishna told him how Karna was able to do that.
"What is this, O diadem-decked Arjuna, that Karna should succeed in crushing thy weapons today with this? Why dost, thou, O hero, lose thy wits? Markest thou not that the Kauravas, (standing behind Karna), are even now shouting in joy? Indeed, all of them know that thy weapons are being baffled by Karna with his.
Krishna then told about how Arjuna slew asuras in every yuga which tells about previous births of Arjuna.
That patience with which, Yuga after Yuga, thou hadst slain persons having the quality of darkness for their weapons, as also terrible Kshatriyas, and Asuras born of pride, in many a battle--with that patience do thou slay Karna today.
Arjuna was even able to wield the sudarshana chakra. krishna requested him to give his sudarshana chakra to kill Karna like Indra killing Namuchi.
Putting forth thy might, strike off the head of that foe of thine with this Sudarsana, of edge keen as a razor, that I give unto thee, like Sakra striking off the head of his foe Namuci, with the thunderbolt.
Well there is already an answer about Arjuna being reincarnation of Nara but I am going to tell about a complete different story given in Padma Purana. I am giving a summary of that story here.
Once during a quarrel between Śiva and Brahmā the former nipped off Brahmā’s head. (For details see under Brahmā). Some drops of sweat appeared on the forehead of the angry Brahmā, and from the sweat which Brahmā wiped with his hand arose a person wearing a thousand shields, bow and quiver. That person was Svedaja. He asked Brahmā what he should do and the former granted him permission to destroy Śiva. He then approached Śiva with bow drawn and the frightened Śiva ran to Viṣṇu and sought refuge. Svedaja followed Śiva and when Viṣṇu, seeing him, raised a loud noise 'Hum'. Śiva prostrated at Viṣṇu’s feet. Śiva extended the skull in his hand towards Viṣṇu requesting something to be given to him. Mahāviṣṇu, who had nothing else to give Śiva, put his right hand into the skull as alms, Śiva wounded the hand with his Śūla (three-pronged weapon) and pure red blood began flowing from the hand into the skull. The blood continued flowing for a thousand years in a length of fifty yojanas and thickness of ten yojanas. At the end of the period Viṣṇu asked whether the skull was not filled yet, and looking into the skull with his three eyes Śiva answered that it was full. Then Viṣṇu stopped the flow of blood, and Śiva, in the presence of Viṣṇu, looked into the blood for a thousand years and stirred it with his hand. The blood gradually turned into a bubble, and a person possessing thousand hands and as glowing as fire appeared in the skull. He had a crown on his head and he held in his hands a bow and quiver. He wore gloves on his hands. And, that was Raktaja, an incarnation of Nararṣi. Looking at Raktaja, Śiva told Viṣṇu thus: "This master in archery is Nara. You spoke Nara, and let his name, therefore be Nara. Oh Nārāyaṇa, you both will be called Naranārāyaṇas. This Nara will be of help to you on behalf of the Devas and also in the sustenance and protection of the world. He will further help you to kill the asuras. Nara, the great intellectual that he is, will become a muni, of surpassing wisdom. Brahmā’s divine fifth head possesses so much of effulgence. Nara is created from that effulgence and also from the blood from your hands and my look at it. He will annihilate all enemies in war. He will be a terror to those persons who cannot be conquered by you, Indra and the other Devas. While Viṣṇu stood there amazed Raktaja praised him and Śiva with folded hands and asked from the skull what he should do. Then Śiva ordered him thus: You kill this asura (Svedaja) created by Brahmā with his own effulgence." And Śiva led Raktaja out of the skull by his hands and told him again:—"Look, here lies the terrible person I spoke about made unconscious by the cry of 'Hum' by Viṣṇu. Awake him immediately." After having said this Śiva disappeared. Nara, in the presence of Nārāyaṇa, kicked the unconscious Svedaja with his left foot, and he came out of his unconscious state. The fierce fight that ensued between Raktaja and Svedaja continued for two years. By then Svedaja had lost everything but one of his shields and Raktaja had only his two arms to fight with. At this stage Vāsudeva (Viṣṇu) in great alarm went and asked Brahmā whether Raktaja might not kill Svedaja. Brahmā answered, 'In the next birth Nara may defeat Svedaja'. Saying 'Right, let that be so', Viṣṇu returned to the battlefield and withdrew them from fighting with the assurance that they would be given an opportunity to fight again during the period of the Kali and the Dvāpara yugas.
The Swedja was born as Karna while Raktja was born as Arjuna.