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.)