Un Bac C en poche, Bruno Salomone débute sa carrière sur les planches au milieu des années 90. Il écume les cafés-théâtres avec des spectacles comiques dans lesquels il impose un genre basé sur l'absurde. Après sa participation à l'émission télévisée Graines de Stars en 1996, son passage sur la scène parisienne du Carré Blanc est décisif : il y fait la connaissance d'Eric Collado, Eric Massot, Emmanuel Joucla et Jean Dujardin, avec lesquels il forme en 1998 la populaire troupe des "Nous C Nous" qui fera les beaux jours de l'émission La Fiesta de Patrick Sébastien.Entamant une carrière solo dès 2001, il se produit dans des one-man-show où son sketch du cochon d'inde fait fureur, et il est la voix off du jeu Burger Quizz présenté par Alain Chabat sur Canal +. Ses débuts sur grand écran, il les effectue aux côtés de Said Taghmaoui dans Gamer (2001). Il doit toutefois attendre 2004 pour trouver un rôle plus consistant, celui d'un pote encombrant, dans Le Carton. Dans la foulée, il prête sa voix au personnage de Syndrome dans le film d'animation Pixar Les Indestructibles. L'année suivante, Bruno Salomone retrouve son fidèle compagnon de route Jean Dujardin et campe face à lui Igor d'Hossegor, l'adversaire de Brice de Nice.
