Neveu de l'Acrobate Claude Melki, le jeune Gilbert rêve de devenir acteur depuis son plus jeune âge. Son père, antiquaire, l'envoie dans une école d'ébénisterie, mais il n'y reste que quelques mois. A 20 ans, il décide de s'orienter vers la comédie, et multiplie les cours de théâtre. Craignant de ne pas être à la hauteur, il prend pourtant bientôt ses distances avec un milieu qui lui semble hostile, et part vivre pendant plusieurs années en Italie.

Après un premier rôle coupé au montage dans Betty, Gilbert Melki accède à la notoriété en 1997 grâce à La Vérité si je mens ! de Thomas Gilou. Il y incarne Patrick Abitbol, homme d'affaires baratineur, un rôle qu'il reprendra dans la suite de cette comédie à succès en 2001. Doublure de Dolores Chaplin dans La Patinoire, l'acteur prouve rapidement qu'il peut jouer d'autres rôles que les Pieds-noirs exubérants. Dealer déjanté pour de Caunes (Les Morsures de l'aube), il séduit Nathalie Baye dans Vénus beauté et Karin Viard dans Reines d'un jour.

En 2003, Gilbert Melki incarne Manise, policier désabusé marié à une toxicomane, l'un des personnages-pivots de l'audacieuse trilogie de Lucas Belvaux, une composition à fleur de peau qui bluffe la critique. Adversaire d'Auteuil dans le western médiéval Rencontre avec le dragon, il interprète l'époux de Catherine Deneuve dans Les Temps qui changent de Techiné (2004), après avoir campé son amant dans Au plus près du paradis. Emouvant en père absent (Monsieur Ibrahim et les fleurs du Coran), l'acteur à la mâle assurance inspire nombre de réalisatrices, de Ronit Elkabetz à Emmanuelle Cuau en passant par Claire Simon.

Après avoir renoué avec la comédie, sur un mode plus grinçant (Crustacés et coquillages et Palais royal ! en 2005), Gilbert Melki, très présent sur les écrans en 2007 (il trouble Isabelle Carré dans Anna M.), s'illustre dans deux polars, une grosse production (Le Deuxième souffle, dans lequel il reprend le rôle crée par Marcel Bozzuffi) et un premier film, Le Tueur. Son fort potentiel comique aidant, il interprète le personnage principal de Made in Italy, dans lequel il retrouve Amira Casar (après La Vérité si je mens). Il apparaît au casting de la super-production Largo Winch (2008), adaptée de la bande-dessinée du même nom, puis se glisse dans la peau d'un flic au grand cœur dans Complices (2009) aux côtés d'Emmanuelle Devos.

Pour cette nouvelle décennie, Gilbert Melki revient à son premier amour, la comédie. On le retrouve ainsi à l'affiche du délirant Le Mac (2010) de Pascal Bourdiaux, dans lequel il campe un dangereux gangster, un genre de personnage qu'il affectionne particulièrement puisqu'il incarne, la même année, un terrifiant mafieux dans L'Avocat de Cédric Anger. En 2012, Gilbert Melki range les armes et ressort son plus beau costume, celui de Patrick Abitbol, le milliardaire juif le plus connu du cinéma français, dans La Vérité si je mens ! 3, dernier volet de la célèbre trilogie.