Benaldjia is an Arabic surname. Notable people with the surname include:

 Billel Benaldjia (born 1988), Algerian footballer
 Mehdi Benaldjia (born 1991), Algerian footballer

Arabic-language surnames