Data hiding in halftone images is a challenging task since these images are very susceptible to alterations. Current steganographic methods for these types of images either embed the data after the image is completely halftoned or modify the halftoning process for embedding purposes. In this paper we present a third type of steganography which performs the embedding by altering the grayscale image prior to its conversion to the halftone form. The goal of the proposed algorithm is to minimize the amount of alterations that are caused in the grayscale image. We compared our algorithm with a secure steganographic method. Also an effective steganalytic attack is applied to show the security of the proposed algorithm and the secure capacity of the proposed method was calculated to be 2% of bi-level image size while the secure capacity of its counterpart was calculated to be under 1%. It is shown that the proposed algorithm in terms of visual quality and security, as compared to the existing algorithms, produces superior results.