When did Krishna first meet Vishnu's bird Garuda?

Question

The Srimad Bhagavatam describes how Krishna flew on the back of Garuda to kill the demon Narakasura, which is the inspiration for the holiday Deepavali:

After Bhauma [Narakasura] had stolen the earrings belonging to Indra’s mother [Aditi], along with Varuṇa’s umbrella and the demigods’ playground at the peak of Mandara mountain, Indra went to Lord Kṛṣṇa and informed Him of these misdeeds. The Lord, taking His wife Satyabhāmā with Him, then rode on Garuḍa to Prāgyotiṣa-pura, which was surrounded on all sides by fortifications consisting of hills, unmanned weapons, water, fire and wind, and by obstructions of mura-pāśa wire.

My question is, is this the first time that Vishnu's incarnation Krishna met Vishnu's bird Garuda? Or did he meet him earlier than that?

A couple chapters earlier, there's a description of Krishna's chariot already having a flag of Garuda on it:

My dear King, Kṛṣṇa and Balarāma mounted Kṛṣṇa’s chariot, which flew the flag of Garuḍa and was yoked with tremendously swift horses, and pursued Their elder’s murderer.

When did Krishna first put Vishnu's Garuda flag on his chariot? Did he use it ever since he started riding chariots in Mathura, since unlike Rama he always knew he was Vishnu? Or did he start using it after some encounter with Garuda?

Note that Garuda is referred to in the story of Krishna defeating the serpent Kalinga, but the two don't actually meet then.

(On a side note, Garuda also had an encounter with Vishnu's incarnation Rama, where he saves Rama and Lakshmana from the snake weapons of Indrajit, as I discuss in this answer.)

Answer 1

The Harivamsam, a part of the Mahabharata, gives us the story when Krishna and Balarama try to save the kingdom from Jarasandha. In the process, their grandfather (Kamsa's father and king) advises them to proceed from the south. In this process, they encounter Parasurama who them guides them to a place where Garuda provides them with weapons.

Answer 2

The first time Garuda meets with his Lord during Krishna Leela, is when, after having defeated Kālayavana and settling the Yadavas in Dwaraka, Krishna and Balarama ascend the Gomanta (Pravarsana) mountain, being pursued by Jarasandha’s vast army. It is at this time when they’re relaxing on the mountain, that Garuda comes and returns Vishnu’s crown to him. Quoting the incident from Harivamsa and Srimad Bhagavatam.

From the Harivamsa:

As they were talking to each other (comfortably) as though they were at home, the son of vinatA (garuDa) arrived there immediately with tremendous speed, ready for battle, with splendour, with the marks of the daitya's strikes and smears of divine pastes on his body, one who praises the victory of deva-s. As Vishnu was sleeping in the divine milk ocean, the residence of Varuna, Vishnu’s crown was stolen by the daitya, vairochana. A terrible battle was fought by garuDa for his preceptor with splendour, with the daitya and his followers for the crown, in the middle of the ocean. The best among the birds freed the crown of viShNu, left the place and reached the sky, the residence of gods, quickly. After accomplishing the task, he saw his preceptor viShNu on the (gomantaka) mountain. garuDa was flying with the crown hanging from his beak, as if he was playing. He saw Vishnu in the form of a human on the peak of the king of mountains, without any external activity, like a human being without a diadem. Garuda, the best among birds, seeing his condition, left the crown, from the sky, happily on viShNu's head. That crown, as it fell, got fixed on the head of upendra (kR^iShNa) without tying.
-Harivamsa, Vishnu Parva, Chapter 41, verses 37-44

From the Srimad Bhagavatam:

On the mountain, they went up the peak called Pravarsana where clouds always sent forth their showers without break... In the meanwhile, in the milky ocean the best among oceans which is the abode of the God of gods, Vishnu, the wielder of conch, discus and a mace, the glorious mighty-armed Bali, the son of Virocana who visited it, took away the crown of the God of gods which was studded with costly jewels. ...Having come to know that the diadem was taken away by the Danava hero, Garuda, the king of birds, and the incharge protector of the city, instantly pursued him. Overtaking the irresistible king of Danavas on the way and putting up a terrible fight with him, he van-quished the prominent demon. Taking away from him the crown, a veritable heap of jewels, which was brilliant like the Sun, he (Garuda) on his way back saw lord Hari, the son of Devaki. He was sitting along with his elder brother on the beautiful and the best of mountains known as Gallants. He immediately placed on his head that heavenly ornament — Vishnu’s crown. Bowing down to his feet with his own head, he began to sing his praise. I am Garuda, the son of Vinata, your humble servant. O Lord ! Be pleased to command me what I should do." Sri Shuka said : Addressing the God of gods thus, Garuda, the king of birds, knelt before him on the ground, bowed him and stood before him with folded palms. Seeing Garuda the prominent one among birds, Krsna the greatest of Yadavas, with his countenance blooming with affection, touched his head (the best part of the body) with hands. "You may go wherever you like, O blessed one. Come in time when you will be remembered by me.” Commanding him thus, he discharged him.....
-Srimad Bhagavatam 10. (See below)

The above incident is placed between the current ŚB 10.50.40 and ŚB 10.50.41 in Vijayadhvaja Tirtha’s version, as stated by Motilal Banarsidas.

---

^{Note: The order of the events is little unclear, especially Harivamsa. The answer is following the order given in the current Srimad Bhagavatam. The ascent of Gomanta (Pravarsana) and crown incident is given in Vijayadhvaja’s version, but the verses that where they are found, are not in continuity and as explained above, have been inserted as part of one of Jarasandha’s first attacks. A plain reading will reveal that it should be after Kalayavana’s destruction. More so from the above verses we can see that the peak of Gomanta mountain is called Pravarsana and hence this incident should find mention after ŚB 10.52.10 in the Pravarsana episode. Regardless of the order, the Gomanta ascension, wherever it be placed, is the first time of the meeting.}