After Judas by transgression fell from his apostleship (Acts 1: 25), and hanging himself out of despair ended his life with a wretched and shameful death (Matt. 27: 5), then, that the number of the Twelve not be lacking, all the disciples gathered in one place after the Ascension of the Savior (the number of men and women being 120), and they chose two men from among them, Joseph, called Barsabas, who was also surnamed Justus, and Matthias, and they set them in the midst. Then they prayed to God and cast lots, "and the lot fell upon Matthias, and he was numbered with the eleven Apostles" (Acts 1: 15-26). And thus, having taken the place of Judas, Matthias fulfilled the work of apostleship and the prophecy concerning Judas, which the Holy Spirit foretold by the mouth of David: "And his bishopric let another take" (Ps. 108:7). After this, it is said, Matthias preached the Gospel in Ethiopia, and completed his life there in martyrdom.
According to Nikephoros (Historia eccl., 2, 40), Matthias first preached the Gospel in Judaea, then in Ethiopia (made out to be a synonym for the region of Colchis, now in modern-day Georgia) and was crucified in Colchis. A marker placed in the ruins of the Roman fortress at Gonio known as Apsaros in the modern Georgian region of Adjara claims that Matthias is buried at that site. However, this is unverifiable as the Georgian government currently prohibits digging near the traditional gravesite.
Read more about Apsaros Fortress in Gonio here and see the video below.