Sedentary lifestyle and excessive energy intake are prominent contributors to obesity; a major risk factors for the development of insulin resistance, type 2 diabetes and cardiovascular diseases. Elucidating the molecular mechanisms underlying these chronic conditions is of relevant importance as it might lead to the identification of novel anti-obesity targets. The purpose of the current study is to investigate differentially expressed proteins between lean and obese subjects through a shot-gun quantitative proteomics approach using peripheral blood mononuclear cells (PBMCs) extracts as well as potential modulation of those proteins by physical exercise. Using this approach, a total of 47 proteins showed at least 1.5 fold change between lean and obese subjects. In obese, the proteomic profiling before and after 3 months of physical exercise showed differential expression of 38 proteins. Thrombospondin 1 (TSP1) was among the proteins that were upregulated in obese subjects and then decreased by physical exercise. Conversely, the histone deacetylase 4 (HDAC4) was downregulated in obese subjects and then induced by physical exercise. The proteomic data was further validated by qRT-PCR, Western blot and immunohistochemistry in both PBMCs and adipose tissue. We also showed that HDAC4 levels correlated positively with maximum oxygen consumption (VO2 Max) but negatively with body mass index, percent body fat, and the inflammatory chemokine RANTES. In functional assays, our data indicated that ectopic expression of HDAC4 significantly impaired TNF-α-dependent activation of NF-κB, establishing thus a link between HDAC4 and regulation of the immune system. Together, the expression pattern of HDAC4 in obese subjects before and after physical exercise, its correlation with various physical, clinical and metabolic parameters along with its inhibitory effect on NF-κB are suggestive of a protective role of HDAC4 against obesity. HDAC4 could therefore represent a potential therapeutic target for the control and management of obesity and presumably insulin resistance.