Accurate prediction of the translation initiation site (TIS) is an important issue for prokaryotic genome annotation. However, it is still a challenge for the existing methods to predict the TIS in the genomes over a wide variety of GC content. Besides, the existing methods have not yet undergone a comprehensive evaluation, leaving prediction reliability as a largely open problem. A new algorithm MED-StartPlus, a tool that predicts TIS in prokaryotic genomes with a wide variety of GC content was presented. It makes several efforts to model the nucleotide composition bias, the regulatory motifs upstream of the TIS, the sequence patterns around the TIS, and the operon structure. Tests on hundreds of reliable data sets, with TISs confirmed by experiments or having annotated functions, show that the new method achieves a totally high accuracy of TIS prediction. Compared with existing TIS predictors, the method reports a totally higher performance, especially for genomes that are GC-rich or have complex initiation mechanisms. The potential application of the method to improve the TIS annotation deposited in the public database was also proposed.