Which tribe did Paul belong to? I came across below two verses when I am reading through my bible(Telugu language). 

To me, these two statements seem to contradict each other: 

Acts 21: 29 


  But Paul said, "I am a man who am a Jew of Tarsus, a city of Cilicia, a citizen of no mean city; and I beseech thee, suffer me to
  speak unto the people." (empahsis added)


Romans 11:1


  I also am an Israelite of the seed of Abraham, of the tribe of Benjamin 


Doesn't the first passage mean he is from the tribe of Judah?. 

Which tribe did he belong to: Judah or Benjamin?
The term "Jew" is an Anglicization of "Judean" which comes from the Greek Ἰουδαῖος (Ioudaios). Technically, it can simply be a regional distinction, that is someone who is from Judea. But it can of course represent one's ethnicity. Greek who happened to grow up in Judea would not have identified himself as a Judean.

In the book of Esther, the Hebrew "Yĕhuwdiy" (יְהוּדִי) is translated Jew, but in this case the Hebrew is etymologically connected to Judah (Judahite, or Jehudite). Though not all the Israelites in Esther are Judahite, this term is used to encompass all of them, showing that it has become, even at the time of Esther's writing, a universal term.

In the Israelite's return from Babylonian exile in around 500 BC, only the tribes of Judah, Benjamin and Levi (who had been in the southern kingdom of Judah when taken captive by Babylon) returned as representative tribes. While remnants of other tribes did exist, only these three return in large numbers and with intact genealogies.

The name Judah, as before in the kingdom of Judah, continued to dominate. In Greek it became Judea, and thus we have Judeans.

So while it can be technically taken as "Judahite", the term "Jew" was expanded to refer to all of the Israelites of Judea.

Therefore, Paul is a Jew, of the Tribe of Benjamin. Both statements are correct and consistent.