Aims. The purpose of this paper is to detect and investigate the nature of long-term radial velocity (RV) variations of K-type giants and to confirm planetary companions around the stars. Methods. We have conducted two planet search programs by precise RV measurement using the 1.8 m telescope at Bohyunsan Optical Astronomy Observatory (BOAO) and the 1.88 m telescope at Okayama Astrophysical Observatory (OAO). The BOAO program searches for planets around 55 early K giants. The OAO program is looking for 190 G-K type giants. Results. In this paper, we report the detection of long-period RV variations of three K giant stars, HD 40956, HD 111591, and HD 113996. We investigated the cause of the observed RV variations and conclude the substellar companions are most likely the cause of the RV variations. The orbital analyses yield P = 578.6 $\pm$ 3.3 d, $m$ sin $i$ = 2.7 $\pm$ 0.6 $M_{\rm{J}}$, $a$ = 1.4 $\pm$ 0.1 AU for HD 40956; P = 1056.4 $\pm$ 14.3 d, $m$ sin $i$ = 4.4 $\pm$ 0.4 $M_{\rm{J}}$, $a$ = 2.5 $\pm$ 0.1 AU for HD 111591; P = 610.2 $\pm$ 3.8 d, $m$ sin $i$ = 6.3 $\pm$ 1.0 $M_{\rm{J}}$, $a$ = 1.6 $\pm$ 0.1 AU for HD 113996.