In this paper, an improved lossless data hiding method with histogram shifting for medical images is proposed. In general, medical images consist of many pure black and white points. In the previous studies, it may need a lot of data as a location map to reconstruct the watermark and the cover image. To solve this problem, we present a new method to record the location map. We use two bits for each block to record the information of histogram shifting and one bit to denote the change of each pixel value on the cover image. The purpose of the former two bits is to avoid wrong information in the extracting process, while that of the latter one is to avoid overflow and underflow. Experimental results show that our method can reduce the size of location map up to 95.04% compared to the previous studies.