Invertible steganography is a kind of information hiding, in which a secret message is embedded in a carrier in such a way that the human visual system is less sensitive. Moreover, the original media is completely retrieved after the secret message is extracted. This chapter proposes a novel invertible steganography scheme with high embedding capacity using two-dimensional histogram shifting in the transform domain. We investigated that the DCT-quantized coefficients of each pair of similar blocks in the left and right views of stereo image commonly meet to values, and the secret bits are first partitioned into 3-bit groups and encoded into decimal form. The embedding direction histogram (EDH) is built and used for embedding. By using EDH to shift the middle frequency DCT-quantized coefficients of the two-dimensional histogram the proposed scheme archives the trade-off between imperceptibility and embedding capacity. The experimental results indicated the method had better performance in comparison to previous schemes.