Barnabas was the senior member of their partnership. Barnabas had been a wealthy landowner. Barnabas had received the spirit and the gospel directly from the apostles in Jerusalem. Barnabas had been selected by thousands of people to be in charge of their food. Barnabas had been an apostle of Peter, before he was an apostle of the Holy Spirit. Barnabas had the deeper resume. Barnabas had more experience. Barnabas had Paul's admiration and respect.
Barnabas helped send Paul away from Jerusalem, retrieved Paul from Tarsus and led Paul to Antioch. Barnabas is mentioned before Paul in Acts until Paul becomes the chief speaker at Antioch Pisidia. From that point on Luke rotates their name order, but it was still Barnabas whom the Lycaonians pegged as Zeus. Barnabas and Paul went to Barnabas' homeland of Cyprus but Paul and Barnabas turned back after Derbe instead of going through the Lion's Gate into Paul's homeland of Cilicia. In their final act as co-workers, Barnabas and Paul appointed elders in all three (or four?) churches on that return trip.
Barnabas had known christian elders in Jerusalem. Paul never lived in Jerusalem as a believer. But Antioch was the first gentile church in the world, and Luke shows us that congregation could handle crisis level decisions without reference to elders, which suggests the church in Antioch may never have recognized any such officers. Given all of the above, we should emphasize that it was most likely Barnabas (with Paul) who decided to appoint "elders" in four brand new Galatian churches.
Unfortunately, however, those elders weren't worth a whole lot of practical help when the Judiazers wreaked havoc in South Galatia. Barnabas never saw that aftermath, so far as we know. Paul went through each town some time after the crisis (and after his letter) and it was Paul who laid eyes on the state of the peoples whose brand new, possibly too quickly appointed elders had been impotent to prevent such catastrophe.
There is one sentence in 1st Thessalonians that some say is about elders, but it more likely refers to Silas and Timothy. If that's true, then we have no evidence Paul appointed elders in Greece during all of his second church planting journey. And why should he have done so, after Galatia? The strong suggestion of all this evidence is that Barnabas was behind the elder appointments in Galatia and Paul sought the Lord about improving the arrangement for a number of years, before appointing (recognizing) who was qualified, a few years later on.
Philippi looks like the next place Paul appointed elders, on his way to Illyricum or else right before Luke left, at the Passover of 57 AD, six and a half years into the life of that church! Paul probably handed the letter we call "1st Timothy" to Timothy in person, one week after that Passover, in Troas. And at that moment, Timothy read about a topic he'd not been exposed to for almost a decade. No wonder Paul needed to be so explicit with his instructions on how to select them.
Paul's instructions to Timothy (and later, to his old colleague Titus) demonstrate that a group of new believers needed time to get to know one another before the whole congregation could recognize who was or was not qualified to be responsible for oversight. By the way, just for the record, and in case you're wondering, I like Elders. But I prefer good ones. ;-)
To sum up: It seems Barnabas was the primary voice in the decision to appoint elders so early in Galatia. And it very much looks like Paul rejected that 'early appointment' approach for the rest of his ministry. This does not necessarily mean Paul temporarily rejected the concept or practice of elders at all. This only suggests Paul somehow determined that "old men" needed to be old in the church.
It is also possible Paul spent those years reflecting before the Lord about what christian eldership was really supposed to be like (or for that matter, gentile christian eldership).
Bill Heroman, Amateur Academic