Holebas was born on June 27, 1984 in Aschaffenburg, Germany, to a Greek father and an Uruguayan mother. He started his professional football career at Munich 1860 in 2002 and, in 2010, was acquired by Olympiakos. In the summer of 2014 he was transferred to Serie A-club AS Roma. In the summer of 2015 he joined Watford in the English Premier League.
In 2011, Holebas received Greek citizenship and debuted with the National Football Team of Greece in a 1-1 friendly against Russia. So far he has been capped 38 times, scoring one goal in a friendly against the Republic of Ireland.
He insists on still being called "Holebas" even though his citizenship papers give his surname as "Cholevas".