Protein adsorption at solid surfaces has received intense focus due to its high relevance to biotechnological applications. In alternative to experimental approaches, computational methods such as molecular dynamics (MD) simulations are frequently employed to simulate the protein adsorption process and to study molecular interactions at the interfacial region. However, a successful simulation of the adsorption process depends largely on the initial adsorbed protein orientation on the surface. To avoid sampling protein trajectory which will eventually fail to adsorb, a workaround is to first determine the preferred orientations of the protein relative to the surface and use them as starting structures in MD simulations. Here, we present the first application of particle swarm optimization (PSO) to search for the low energy docking poses of a protein molecule on a solid surface. Performing rigid-body translation and rotation of the protein with energy minimization and empirical scoring function, our search algorithm successfully located the low energy orientations of the lysozyme molecule on a hydrophobic PTFE surface. Nine out of ten predicted docking poses are energetically more favorable than all poses sampled using a brute-force search. Three sets of major adsorption sites are identified for the lysozyme and they are in good agreement to results obtained by long MD simulations; novel adsorption sites are also identified from the lowest energy docking pose. Our method provides a reliable way to predict the optimal protein orientations useful for computational studies of protein-surface interactions.