Dejan Kelhar speelde voor de jeugd van NK Brežice, waar hij in 2002 werd weggehaald door NK Krško uit de Sloveense tweede klasse. Hij speelde daar twee seizoenen en verhuisde toen naar eersteklasserPublikum Celje. Na een half seizoen reeds ruilde hij Celje voor Olimpija Ljubljana, maar keerde op het einde van dat seizoen terug naar Celje. In juni 2006 werd hij voor 100.000 euro getransfereerd[4] naar het Duitse SpVgg Greuther Fürth, dat in de Tweede Bundesliga uitkwam. In zijn eerste seizoen speelde Kelhar acht wedstrijden voor Greuther Fürth, maar bracht het daarna niet verder dan de beloftenploeg. In oktober 2007 verliet hij Fürth[5] en in januari 2008 keerde Kelhar terug naar Publikum Celje[6]. Op 31 januari2009 tekende Kelhar een contract voor 2,5 seizoenen bij Cercle Brugge[2], om daar in februari 2011 te vertrekken. Hij tekende voor 2,5 jaar bij het Poolse Legia Warschau.