Reduced activity of enzymes upon immobilization is a major challenge for the industrial use of enzymes. Enzyme-surface interactions and interactions between the immobilized enzymes are thought of as primary reasons for the reduced activity. In the current paper, we study the thermal and structural stability of proteins on a patterned hydrophobic surface in the framework of a hydrophobic-polar lattice model. Our results indicate that, while a homogeneous hydrophobic surface denatures the proteins, carefully patterned surfaces can dramatically increase the stability of adsorbed proteins. The size, shape, and the distance between surface patterns play a significant role in determining the stability of proteins. When the spacing between the patterns is large, maximum stability is observed when the surface pattern is complementary to the exposed hydrophobic domain of the protein, while at smaller spacing, patterns with lower hydrophobicity stabilize the protein more compared to the complementary pattern. The findings from the paper can be rationalized to design novel enzyme-specific surfaces for immobilization with enhanced enzymatic activity.