We report the first proteomic analysis of the insoluble sub-proteome of the alkaliphilic and halotolerant deep-sea bacterium Oceanobacillus iheyensis HTE831. A multidimensional gel-based and gel-free analysis was utilised and a total of 4352 peptides were initially identified by automated MS/MS identification software. Automated curation of this list using PROVALT reduced our peptide list to 467 uniquely identified peptides that resulted in the positive identification of 153 proteins. These identified proteins were functionally classified and physiochemically characterised. Of 26 proteins identified as hypothetical conserved, we have assigned function to all but four. A total of 41 proteins were predicted to possess signal peptides. In silico investigation of these proteins allowed us to identify three of the five bacterial classes of signal peptide, namely: (i) twin-arginine translocation; (ii) Sec-type and (iii) lipoprotein transport. Our proteomic strategy has also allowed us to identify, at neutral pH, a number of proteins described previously as belonging to two putative transport systems believed to be of importance in the alkaliphilic adaptation of O. iheyensis HTE831.